Intuition Explained || Graph, DFS based approach || C++ Clean Code
Intuition :\n\n Idea here is to first create a graph, such that there is a edge between two bombs i and j,\n\n\t if when we detonate ith bomb, then jth bomb lie
**Intuition :**\n\n* Idea here is to first create a graph, such that there is a edge between two bombs `i` and `j`,\n\n\t* if when we detonate `ith` bomb, then `jth bomb` lies within its **proximity** (as given in problem stmt),\n\t* i.e iff **`distance between centers <= radius of ith bomb`**\n* To create graph, simply we need to loop over `bombs` list, and then for each `bomb i`, \n\t* we need to check if a `bomb j` lies withing its **proximity**. \n\t* In this way we will create `deto_adj`, where `deto_adj[i]` is list of all bombs that lie in its proximity\n\n\t\t\tEx : say we have i = 2, n = 4. Also, say j = 0, 3 are nodes that lie within its proximity\n\t\t\t\n\t\t\t# 2 -> 0, 3\n\t\t\t\n\t\t\tThen, deto_adj[i] = deto_adj[2] = {0, 3} \n\t\t\t\n\t\t\tNote: This is a directed edge. \n\t\t\t\n\t\t\t\n* So, once we have our graph [adjacency list], next for each bomb in `bombs` list, simply do a **DFS (or BFS)**, and \n\t* ***count the number of bombs (nodes) it can visit.***\n* In then end we need to return the maximum count among all the bombs.\n\n------------------\n# Code : DFS Approach\n\n```\nclass Solution {\npublic:\n    \n\t// Check if (x2, y2) lie within the proximity of (x1, y1)\n    bool check(long long x1, long long y1, long long x2, long long y2, long long d) {\n        long long x = (x1-x2) * (x1-x2);\n        long long y = (y1-y2) * (y1-y2);\n        \n        return (x + y  <= d * d);\n    }\n    \n\t// DFS to detonate "node" , and count number of other nodes \n\t// that can be detonated (visited) from currernt node.\n    int detonate(vector<vector<int>>& adj, vector<bool>& vis, int node, int n) {\n        \n        int count = 1;\n        vis[node] = true;\n        \n        for(auto& adjnode : adj[node]) {\n            if(!vis[adjnode]) {\n                count += detonate(adj, vis, adjnode, n);\n            }\n        }\n        \n        return count;\n    }\n    \n    int maximumDetonation(vector<vector<int>>& bombs) {\n        \n        int n = bombs.size();\n        \n        int maxBombs = 0;\n        \n\t\t// Adjacency list to store all edges for nodes [0, n-1]\n\t\t// i.e all bombs that lie within proximity of node\n        vector<vector<int>> deto_adj(n);\n        \n\t\t// Create graph by connecting directed edges\n\t\t// Between ith and jth node\n        for(int i=0; i<n; i++) {\n            for(int j=0; j<n; j++) {\n                if(i != j && check(bombs[i][0], bombs[i][1], bombs[j][0], bombs[j][1], bombs[i][2])) {\n                    deto_adj[i].push_back(j);\n                }  \n            }\n        }\n        \n\t\t// For each bomb, do simple DFS (detonate)\n\t\t// And get count of nodes that can be visited from current node\t\t\n        for(int i=0; i<n; i++) {\n            vector<bool> vis(n, false);\n            \n\t\t\t// Also update maximum count\n            maxBombs = max(maxBombs, detonate(deto_adj, vis, i, n));\n        }\n        \n        return maxBombs;\n    }\n};\n```\n\nNote: Instead of DFS, you can also use BFS. Both approach is correct.\n\n------------------\n\n**Complexity :** \n\n* Time : `O(N * N)` , N is number of bombs\n\t* To create `deto_adj` \n\t* And then for each bomb node, perform DFS\n\n* Space : `~ O(N * N)`, to create adjacency list\n\n***If you find this helpful, do give it a like : )***
['Math', 'Depth-First Search', 'Graph', 'Geometry']