2101. 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

#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

#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