VERY Intuitive SOLUTION!! AMAZING DSA CONCEPTS USED!!! MUST SEE!!!
This question deserves more attention as it is one of the most beautiful problems I\'ve seen! Absolute JOY !!\n# Intuition\n Describe your first thoughts on how
## This question deserves more attention as it is one of the most beautiful problems I\'ve seen! Absolute JOY !!\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nNow, the biggest question in anyone\'s mind when they first see this question is "How is this a graph\'s question"? And that\'s where the solution is! Once you figure it out, its just a matter of applying DFS or BFS!!\n\nThe hint is given in the question itself! Now, consider yourself on the first bomb, if there are any other bombs in your blast radius, they will explode when YOU explode! So, isn\'t that similar to you having a path to those bombs?\n\nSimilarly, every bomb will have its own range of other bombs. You will observe a graph like structure getting formed where the paths are basically saying that this bomb can be "reached" or exploded.\nYou just need to find the max depth of the created graph!\n\n## My solution is kind of not very efficient, but it is simple, intuitive, focuses on core DSA concepts and solves the problem gracefully!\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nCoordinate Geometry distance formula is used to calculate distance between any two points\n\nFirst, you need to create the graph!\n\nFor that, I have used the adjacency list method implemented using an unordered MAP! Where each key is the vertex having a vector of elements which are the nodes it can reach aka the bombs within the blast radius.\n\nTo check if the bomb is in the blast radius, if the sum of radius of the two bombs is greater or equal to the distance between the centers of the bombs, then the said bombs are in blast radius of each other. That\'s exactly what I\'ve done here.\nFor every ith bomb, i check it with all the bombs except for the case where i==j as its comparing the bomb with itself.\n\nI am using a set as my visited tool, mostly for using the size function to get my answer!\nI apply DFS on every "key" of my map or adj. list and keep on taking max of size of visited set as my answer!\n\n# Complexity\n- Time complexity: O(n^2)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    typedef long long LL;\n    LL distancesq(LL x1, LL y1, LL x2, LL y2){\n        return (LL)((x1 - x2) * (x1 - x2)) + ((y1 - y2) * (y1 - y2));\n    }\n    int max(int a, int b){\n        return a > b ? a : b;\n    }\n    void dfs(unordered_map<int, vector<int>> &umap, int u,unordered_set<int> & visited){\n        visited.insert(u);\n        for(int &v : umap[u]){\n            if(visited.find(v) == visited.end()){\n                dfs(umap, v, visited);\n            }\n        }\n    }\n    int maximumDetonation(vector<vector<int>>& bombs) {\n        // r >= d for a bomb to detonate other bomb\n        unordered_map<int, vector<int>> umap;\n        int count = 0;\n        int n = bombs.size();\n        for(int i = 0 ; i < n ; i++){\n            for(int j = 0; j < n ; j++){\n                if(i == j)\n                    continue;\n                LL x1 = bombs[i][0];\n                LL x2 = bombs[j][0];\n                LL y1 = bombs[i][1];\n                LL y2 = bombs[j][1];\n                LL centre_dist = distancesq(x1, y1, x2, y2);\n                LL r = bombs[i][2];\n                if ((r * r) >= centre_dist)\n                    umap[i].push_back(j);\n            }\n        }\n        int m = 0;\n        unordered_set<int> visited;\n        for(int i = 0; i<n; i++) {\n            dfs(umap, i, visited);\n            m = max(m, visited.size());\n            visited.clear();\n        }\n        return m;\n    }\n};\n```
['Array', 'Math', 'Depth-First Search', 'Graph', 'C++']