Detonate Maximum Bombs, C++ Explained Solution
The problem here can be solved in 2 ways. Using BFS or DFS. We have discussed BFS here because it can reduce down the code needed in DFS to form the graph first
The problem here can be solved in 2 ways. Using **BFS** or **DFS**. We have discussed BFS here because it can reduce down the code needed in DFS to form the graph first. Basically if you see, we have been given a **DIRECTED GRAPH**. Note : **The graph might not be a DAG (Directed Acyclic Graph) cause it might be possible that a series of bombs might blast each other thus forming a cycle. So specifically we are only given a directed graph.** Now simply what we can do is choose each bomb and then perform BFS to obtain all bombs that might get detonated and take maximum among all choices. The implementation is given below :\n\nTime Complexity : O(N^2)\nSpace Complexity : O(N)\n\nCode\n```\nclass Solution {\npublic:\n    int maximumDetonation(vector<vector<int>>& bombs) {\n        ios_base::sync_with_stdio(0);\n        int n = bombs.size();\n        int maxbombs = 0; vector<bool>visited(n,false);\n        for(int i = 0; i<n; i++){\n            queue<int>q; int countbombs = 0;\n            q.push(i);\n            while(!q.empty()){\n                int u = q.front(); q.pop();\n                countbombs++;\n                visited[u] = true;\n                long long x = bombs[u][0],y = bombs[u][1],r = bombs[u][2];\n                for(int j = 0; j<n; j++){\n                    if(!visited[j]){\n                        long long dx = bombs[j][0],dy = bombs[j][1],rd = bombs[j][2];\n                        long long dis = (x-dx)*(x-dx)+(y-dy)*(y-dy);\n                        if(dis<=r*r){\n                            visited[j] = true;\n                            q.push(j);\n                        }\n                    }\n                }\n            }\n            maxbombs = max(maxbombs,countbombs);\n            for(int i = 0; i<n; i++){\n                visited[i] = false;\n            }\n        }\n        return maxbombs;\n    }\n};\n```\n\n**Do Upvote If Found Helpful !**
['Depth-First Search', 'Breadth-First Search', 'Graph', 'C']