[MBFS] lc2101. 引爆最多的炸弹(bfs+有向图建图+思维误区)

1. 题目来源

链接：2101. 引爆最多的炸弹

2. 题目解析

这个问题蛮有意思的，比较考验代码能力。还存在一个思维误区。

为什么不能用并查集？

• 本题是有向图的关系，如：0 引爆 1， 0 引爆 2, 1和2不能互相引爆。那么用了并查集，则将 0,1,2 归结到同一个集合中，计算集合元素将出错。

BFS 思路：

• 将所有的炸弹两两进行判断，如果 a 能引爆 b，则需要加一条有向边 a->b。建出一个有向图。
• 枚举炸弹，i，在有向图中 bfs 搜索 i 能引爆的其他炸弹，将它加入队列，统计次数即可。
• 注意为了不重复遍历，需要开辟 visited 数组进行判重。也是 BFS 常规操作。

坑点：

• 计算时会爆 int，记得开 LL。

这个问题蛮有意思的，bfs 即可，关键是建图这个思维转换能力。后续的处理操作就是一个 bfs 模板，bfs 操作和引爆炸弹的实际过程是一样的，在输出路径上有更大优势。当然 dfs 也可以处理，代码见下方即可。

• 时间复杂度：$O(n^3)$
• 空间复杂度：$O(n^2)$

class Solution {
public:
    typedef long long LL;
    bool check(LL x1, LL y1, LL r1, LL x2, LL y2, LL r2) {
        return ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) <= r1 * r1;
    }

    int maximumDetonation(vector<vector<int>>& bombs) {
        int n = bombs.size();

        vector<vector<int>> edges(n);
        for (int i = 0; i < n; i ++ ) {
            int x1 = bombs[i][0], y1 = bombs[i][1], r1 = bombs[i][2];
            for (int j = 0; j < n; j ++ ) {
                if (i == j) continue;
                int x2 = bombs[j][0], y2 = bombs[j][1], r2 = bombs[j][2];
                if (check(x1, y1, r1, x2, y2, r2)) {
                    edges[i].push_back(j);
                }
            }
        }

        int res = 0;
        for (int i = 0; i < n; i ++ ) {
            vector<int> visisted(n);
            int cnt = 1;
            queue<int> q; q.push(i);
            visisted[i] = 1;
            while (q.size()) {
                int cur = q.front(); q.pop();
                for (int ne : edges[cur]) {
                    if (visisted[ne]) continue;

                    cnt ++ ;
                    q.push(ne);
                    visisted[ne] = 1;
                }
            }
            res = max(res, cnt);
        }

        return res;
    }
};

dfs：

class Solution {
public:
    typedef long long LL;
    bool check(LL x1, LL y1, LL r1, LL x2, LL y2, LL r2) {
        return ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) <= r1 * r1;
    }

    int dfs(vector<vector<int>> &g, vector<int> &vis, int x) {
        vis[x] = true;
        int cnt = 1;
        for (int y : g[x]) {
            if (vis[y]) continue;
            cnt += dfs(g, vis, y); 
        }

        return cnt;
    }
    int maximumDetonation(vector<vector<int>>& bombs) {
        int n = bombs.size();

        vector<vector<int>> edges(n);
        for (int i = 0; i < n; i ++ ) {
            int x1 = bombs[i][0], y1 = bombs[i][1], r1 = bombs[i][2];
            for (int j = 0; j < n; j ++ ) {
                if (i == j) continue;
                int x2 = bombs[j][0], y2 = bombs[j][1], r2 = bombs[j][2];
                if (check(x1, y1, r1, x2, y2, r2)) {
                    edges[i].push_back(j);
                }
            }
        }

        int res = 0;
        for (int i = 0; i < n; i ++ ) {
            vector<int> vis(n);
            res = max(res, dfs(edges, vis, i));
        }

        return res;
    }
};