# 2101. 引爆最多的炸弹
### 题目地址(5936. 引爆最多的炸弹)
### 题目描述
```
给你一个炸弹列表。一个炸弹的 爆炸范围 定义为以炸弹为圆心的一个圆。
炸弹用一个下标从 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:
```python
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)$
> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/5936.detonate-the-maximum-bombs.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.