[2101. Detonate the Maximum Bombs](https://leetcode.com/problems/detonate-the-maximum-bombs/)

--- tags: leetcode --- # [2101. Detonate the Maximum Bombs](https://leetcode.com/problems/detonate-the-maximum-bombs/) --- # My Solution ## Solution 1: DFS ### The Key Idea for Solving This Coding Question Count the number of nodes in the largest component. ### C++ Code ```cpp= #define WHITE (1) #define GRAY (2) #define BLACK (3) class Solution { public: int maximumDetonation(vector<vector<int>> &bombs) { int numBombs = bombs.size(); vector<vector<int>> graph(numBombs); for (int i = 0; i + 1 < numBombs; ++i) { unsigned long xi = bombs[i][0], yi = bombs[i][1], ri = bombs[i][2]; for (int j = i + 1; j < numBombs; ++j) { unsigned long xj = bombs[j][0], yj = bombs[j][1], rj = bombs[j][2]; unsigned long distance = (xi - xj) * (xi - xj) + (yi - yj) * (yi - yj); if (distance <= ri * ri) { graph[i].push_back(j); } if (distance <= rj * rj) { graph[j].push_back(i); } } } int maxBombs = 0; for (int i = 0; i < numBombs; ++i) { vector<int> state(numBombs, WHITE); maxBombs = max(maxBombs, dfs(graph, state, i)); } return maxBombs; } private: int dfs(vector<vector<int>> &graph, vector<int> &state, int currBomb) { state[currBomb] = GRAY; int cnt = 1; for (auto &nextBomb : graph[currBomb]) { if (state[nextBomb] != WHITE) { continue; } cnt += dfs(graph, state, nextBomb); } state[currBomb] = BLACK; return cnt; } }; ``` ### Time Complexity $O(V+E)$ $V$ is the length of `bombs`. $E$ is the number of edges in the graph. ### Space Complexity $O(V+E)$ ## Solution 2: BFS ### The Key Idea for Solving This Coding Question Count the number of nodes in the largest component. ### C++ Code ```cpp= #define WHITE (0) #define GRAY (1) #define BLACK (2) class Solution { public: int maximumDetonation(vector<vector<int>> &bombs) { int numBombs = bombs.size(); vector<vector<int>> graph(numBombs); for (int i = 0; i + 1 < bombs.size(); ++i) { for (int j = i + 1; j < bombs.size(); ++j) { unsigned long xi = bombs[i][0], yi = bombs[i][1], ri = bombs[i][2]; unsigned long xj = bombs[j][0], yj = bombs[j][1], rj = bombs[j][2]; unsigned long distance = (xi - xj) * (xi - xj) + (yi - yj) * (yi - yj); if (distance <= ri * ri) { graph[i].push_back(j); } if (distance <= rj * rj) { graph[j].push_back(i); } } } int maxBombs = 0; for (int i = 0; i < numBombs; ++i) { vector<int> state(numBombs, WHITE); maxBombs = max(maxBombs, bfs(graph, state, i)); } return maxBombs; } private: int bfs(vector<vector<int>> &graph, vector<int> &state, int firstBomb) { queue<int> q; int cnt = 1; q.push(firstBomb); state[firstBomb] = GRAY; while (!q.empty()) { int currBomb = q.front(); q.pop(); for (auto &nextBomb : graph[currBomb]) { if (state[nextBomb] != WHITE) { continue; } q.push(nextBomb); state[nextBomb] = GRAY; ++cnt; } state[currBomb] = BLACK; } return cnt; } }; ``` ### Time Complexity $O(V+E)$ $V$ is the length of `bombs`. $E$ is the number of edges in the graph. ### Space Complexity $O(V+E)$ # Miscellaneous [695. Max Area of Island](https://leetcode.com/problems/max-area-of-island/)