https://leetcode-cn.com/problems/detonate-the-maximum-bombs/
给你一个炸弹列表。一个炸弹的 爆炸范围 定义为以炸弹为圆心的一个圆。
炸弹用一个下标从 0 开始的二维整数数组 bombs 表示，其中 bombs[i] = [xi, yi, ri] 。xi 和 yi 表示第 i 个炸弹的 X 和 Y 坐标，ri 表示爆炸范围的 半径 。
你需要选择引爆 一个 炸弹。当这个炸弹被引爆时，所有 在它爆炸范围内的炸弹都会被引爆，这些炸弹会进一步将它们爆炸范围内的其他炸弹引爆。
给你数组 bombs ，请你返回在引爆 一个 炸弹的前提下，最多 能引爆的炸弹数目。
示例 1：
输入：bombs = [[2,1,3],[6,1,4]]
输出：2
解释：
上图展示了 2 个炸弹的位置和爆炸范围。
如果我们引爆左边的炸弹，右边的炸弹不会被影响。
但如果我们引爆右边的炸弹，两个炸弹都会爆炸。
所以最多能引爆的炸弹数目是 max(1, 2) = 2 。
示例 2：
输入：bombs = [[1,1,5],[10,10,5]]
输出：1
解释：
引爆任意一个炸弹都不会引爆另一个炸弹。所以最多能引爆的炸弹数目为 1 。
示例 3：
输入：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 <= 105
- BFS
- 暂无
刚开始的想法是计算图的最大联通分量，因此使用并查集就可以解决。
后来提交的时候发现有问题。这是因为题目限制了引爆关系指的是：某一个炸弹的引爆范围是否会引爆到其他炸弹的圆心，而不是相交就行。这提示了我们：炸弹 a 引爆炸弹 b 的情况下，炸弹 b 不一定能够引爆炸弹 a。
也就是说我们将炸弹看做是点，炸弹 a 如果能够引爆炸弹 b，那么就有一条从 a 到 b 的边。而并查集无法处理这种关系。
因此我们可以使用 BFS 来做。首先预处理出图，然后对于图中每一点 i 进行 BFS，然后在这 n 次 bfs 中将最大引爆炸弹数记录下来返回即可。
- BFS
- 语言支持：Python3
Python3 Code:
class Solution:
def maximumDetonation(self, bombs: List[List[int]]) -> int:
n = len(bombs)
d = collections.defaultdict(list)
def overlap(i, j):
x1, y1, r1 = bombs[i]
x2, y2, r2 = bombs[j]
return (x1 - x2) ** 2 + (y1 - y2) ** 2 <= r1 ** 2
for i in range(n):
for j in range(i+1, n):
if overlap(i, j):
d[i].append(j)
if overlap(j, i):
d[j].append(i)
ans = 1
for i in range(n):
q = collections.deque([i])
vis = set()
count = 0
while q:
cur = q.popleft()
if cur in vis: continue
vis.add(cur)
count += 1
for neibor in d[cur]:
q.append(neibor)
ans = max(ans, count)
return ans
复杂度分析
令 n 为数组长度。
- 时间复杂度：$O(n^3)$. 其中建图部分时间复杂度为
$O(n^2)$ ，。并且由于每个点的出度最多为 n，因此对于每一个点 i BFS 的时间复杂度为$n^2$ ，由于一共有 n 个点，因此总时间复杂度为$O(n^3)$ 。 - 空间复杂度：$O(n^3)$
此题解由 力扣刷题插件 自动生成。
力扣的小伙伴可以关注我，这样就会第一时间收到我的动态啦~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
