Easy C++ Solution
Intuition\n Describe your first thoughts on how to solve this problem. \nIn this problem, we are given a list of bombs represented by their coordinates (x and y
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIn this problem, we are given a list of bombs represented by their coordinates (x and y) and the explosion radius. The task is to determine the maximum number of bombs that can be detonated by starting with any bomb and detonating all other bombs within its explosion range.\n\nImagine each bomb as a node in a graph. If two bombs are within range of each other, we can consider an edge between the corresponding nodes. The objective is to find the connected component with the maximum number of nodes, as it represents the maximum detonation possible.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nTo solve this problem, we can follow these steps:\n\n1. Initialize an adjacency list to represent the connections between bombs.\n2. Iterate over each bomb and calculate the squared explosion radius (r).\n3. Compare the squared Euclidean distance between each pair of bombs. If it is less than or equal to r, add an edge between them in the adjacency list.\n4. Initialize a variable to keep track of the maximum detonation count (ans).\n5. For each bomb, perform a BFS starting from that bomb to find the number of bombs that can be detonated.\n6. Maintain a queue and a visited array during the BFS.\n7. Start BFS from the current bomb by adding it to the queue and marking it as visited.\n8. While the queue is not empty, process the front element, increment the detonation count, and visit its adjacent bombs if they haven\'t been visited before.\n9. Update the maximum detonation count if the current count is greater.\n10. Repeat steps 5-9 for each bomb.\n11. Return the maximum detonation count as the result.\n\nBy representing the bombs as nodes in a graph and performing a BFS traversal, we can identify the connected component with the maximum number of nodes, which corresponds to the maximum detonation count.\n\n\n\n# Complexity\n- Time complexity: O(N^3)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(N^2)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int maximumDetonation(vector<vector<int>>& bombs) \n    {\n        const int n = bombs.size();\n        vector<vector<int>> v(n);\n\n        for (int i = 0; i < n; i++) \n        {\n            long long r = (long long) bombs[i][2] * bombs[i][2];\n            for (int j = 0; j < n; j++) \n            {\n                if (i != j) \n                {\n                    if ((long long) ((long long) bombs[i][0] - bombs[j][0]) * ((long long) bombs[i][0] - bombs[j][0]) + \n                        (long long) (bombs[i][1] - bombs[j][1]) * ((long long) bombs[i][1] - bombs[j][1]) <= r) \n                    {\n                        v[i].push_back(j);\n                    }\n                }\n            }\n        }\n\n        int ans = 1;\n        for (int i = 0; i < n; i++) \n        {\n            vector<bool> vis(n, false);\n            int mx = 0;\n            queue<int> q;\n            q.push(i);\n\n            while (!q.empty()) \n            {\n                int s = q.size();\n                for (int j = 0; j < s; j++) \n                {\n                    int x = q.front();\n                    q.pop();\n                    vis[x] = true;\n                    mx++;\n                    for (auto p : v[x]) \n                    {\n                        if (!vis[p]) {\n                            q.push(p);\n                            vis[p] = true;\n                        }\n                    }\n                }\n            }\n            ans = max(ans, mx);\n        }\n\n        return ans;\n    }\n};\n\n```
['Breadth-First Search', 'C++']