Easy to Understand with video solution
Intuition\n Describe your first thoughts on how to solve this problem. \nWe have a radius/range for each bomb and every bomb in that radius will explode that wi
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe have a radius/range for each bomb and every bomb in that radius will explode that will start a chain reaction. This implies that we need to constuct a graph where adjecent nodes will be the bomb index in the range.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe\'ll construct a graph whose adj nodes will denote the coordinates of bomb which will explode if Ith bomb exploded.\nNow we\'ll run a DFS on the graph we constructed and calculate the longest chain we have.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n^2) + O(n^2)--> to construct the graph and run dfs for every node.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n^2) --> as we are constructing graph.\n\n# Video Link : \nhttps://www.youtube.com/watch?v=jqzel5CawPA\n\n# Code\n```\nclass Solution {\npublic:\n    void dfs(vector<vector<int>>& graph, int start,vector<bool>& vis,int& len){\n        if(vis[start]) return;\n        vis[start] = true;\n        len++;\n        for(int node:graph[start]){\n            if(!vis[node]) dfs(graph,node,vis,len);\n        }\n\n    }\n    bool isBombInRange(int x1,int y1,int x2,int y2,int radius){\n        float dist = sqrt(pow(x1-x2,2)+pow(y1-y2,2));\n        return ceil(dist)<=radius;\n    }\n    int maximumDetonation(vector<vector<int>>& bombs) {\n        vector<vector<int>> graph(bombs.size());\n        for(int i=0;i<bombs.size();i++){\n            for(int j=i+1;j<bombs.size();j++){\n                // if(i!=j){\n                    int x1 = bombs[i][0];\n                    int y1 = bombs[i][1];\n                    int radius1 = bombs[i][2];\n                    int x2 = bombs[j][0];\n                    int y2 = bombs[j][1];\n                    int radius2 = bombs[j][2];\n                    if(isBombInRange(x1,y1,x2,y2,radius1)){\n                        graph[i].push_back(j);\n                    }\n                    if(isBombInRange(x1,y1,x2,y2,radius2)) graph[j].push_back(i);\n                // }\n            }\n        }\n\n        // printGraph(graph);\n\n        \n        int ans = 0;\n        for(int i=0;i<bombs.size();i++){\n            // if(!vis[i]){\n                vector<bool> vis(bombs.size(),false);\n                int temp = 0;\n                dfs(graph,i,vis,temp);\n                ans = max(ans,temp);\n            // }\n        }\n        return ans;\n    }\n\n    void printGraph(vector<vector<int>>& graph){\n        for(int i=0;i<graph.size();i++){\n            for(int node:graph[i]) cout<<node<<" ";\n            cout<<endl;\n        }\n    }\n};\n```
['Math', 'Depth-First Search', 'Graph', 'Geometry', 'C++']