LeetCode 2101. 引爆最多的炸弹（图的遍历）

输入：bombs = [[2,1,3],[6,1,4]]
输出：2
解释：
上图展示了 2 个炸弹的位置和爆炸范围。
如果我们引爆左边的炸弹，右边的炸弹不会被影响。
但如果我们引爆右边的炸弹，两个炸弹都会爆炸。
所以最多能引爆的炸弹数目是 max(1, 2) = 2 。

输入：bombs = [[1,1,5],[10,10,5]]
输出：1
解释：
引爆任意一个炸弹都不会引爆另一个炸弹。所以最多能引爆的炸弹数目为 1 。

输入：bombs = [[1,2,3],[2,3,1],[3,4,2],[4,5,3],[5,6,4]]
输出：5
解释：
最佳引爆炸弹为炸弹 0 ，因为：
- 炸弹 0 引爆炸弹 1 和 2 。红色圆表示炸弹 0 的爆炸范围。
- 炸弹 2 引爆炸弹 3 。蓝色圆表示炸弹 2 的爆炸范围。
- 炸弹 3 引爆炸弹 4 。绿色圆表示炸弹 3 的爆炸范围。
所以总共有 5 个炸弹被引爆。
 
提示：
1 <= bombs.length <= 100
bombs[i].length == 3
1 <= xi, yi, ri <= 10^5

class Solution {
public:
    int maximumDetonation(vector<vector<int>>& bombs) {
        int n = bombs.size(), x1, y1, r1, x2, y2;
        vector<vector<int>> g(n);
        for(int i = 0; i < n; ++i)
        {
            x1 = bombs[i][0];
            y1 = bombs[i][1];
            r1 = bombs[i][2];
            for(int j = 0; j < n; ++j)
            {
                if(i == j) continue;
                x2 = bombs[j][0];
                y2 = bombs[j][1];
                if(1LL*(x1-x2)*(x1-x2)+1LL*(y1-y2)*(y1-y2) <= 1LL*r1*r1)
                    g[i].push_back(j);
            }
        }
        int ans = 1;
        for(int i = 0; i < n; ++i)
        {
            queue<int> q;
            q.push(i);
            vector<bool> vis(n, false);
            vis[i] = true;
            int ct = 0;
            while(!q.empty())
            {
                int id = q.front();
                q.pop();
                ct++;
                for(int nid : g[id])
                {
                    if(!vis[nid])
                    {
                        vis[nid] = true;
                        q.push(nid);
                    }
                }
            }
            ans = max(ans, ct);
        }
        return ans;
    }
};