有一张 nn 个点的巨大图,由一个集合 dd 描述,如果两个点 i,ji,j 满足 ∣i−j∣∈d∣i−j∣∈d,则在 i,ji,j 间连一条无向边。求连通块个数。
时间: 2024-05-16 10:15:31 浏览: 11
这道题可以用广度优先搜索或深度优先搜索来解决。
我们可以先将所有满足条件的点对连边,然后对每个连通块进行搜索,统计连通块的个数。
具体实现可以使用一个数组 `vis` 来记录每个点是否被访问过,然后对每个未访问过的点进行搜索。在搜索过程中,对于每个与当前节点相邻的未访问过的节点,将其标记为已访问,并将其加入搜索队列中。当队列为空时,当前连通块的搜索结束,连通块的个数加一。
下面是使用深度优先搜索的代码实现:
```python
from collections import deque
n = int(input())
d = set(map(int, input().split()))
graph = [[] for _ in range(n)]
for i in range(n):
for j in range(i + 1, n):
if abs(i - j) in d:
graph[i].append(j)
graph[j].append(i)
vis = [False] * n
cnt = 0
def dfs(u):
vis[u] = True
for v in graph[u]:
if not vis[v]:
dfs(v)
for i in range(n):
if not vis[i]:
cnt += 1
dfs(i)
print(cnt)
```
时间复杂度为 $O(n^2)$,可以通过本题。