输入格式: • 第一行为节点个数(n<= 2000000)和边数(m<= 2030000) ,然后下面每一行为边 的头尾节点 • 输出格式: • 连通分量个数 • 样例输入: 3 1 1 2 样例输出: 2
时间: 2024-01-21 21:03:28 浏览: 21
这是一个基础的图论问题,需要用到深度优先搜索(DFS)或广度优先搜索(BFS)来求解。
以下是DFS的思路:
1. 定义一个visited数组,用来记录每个节点是否已经被访问过,初始值为false。
2. 定义一个邻接表,用来存储图的边信息。
3. 定义一个count变量,用来记录连通分量个数,初始值为0。
4. 从任意一个未被访问的节点开始,进行DFS遍历,遍历到的节点标记为已访问。
5. 对于每个未被访问的相邻节点,进行递归DFS遍历,直到所有相邻节点都被访问过。
6. 遍历完一个连通分量后,count自增1。
7. 重复4-6步,直到所有节点都被访问过。
以下是代码实现:
```python
n, m = map(int, input().split())
visited = [False] * (n+1)
graph = [[] for _ in range(n+1)]
for _ in range(m):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
def dfs(node):
visited[node] = True
for neighbor in graph[node]:
if not visited[neighbor]:
dfs(neighbor)
count = 0
for i in range(1, n+1):
if not visited[i]:
dfs(i)
count += 1
print(count)
```
时间复杂度为O(n+m),空间复杂度为O(n+m)。