80242 - 2026编程挑战赛Python提高组42
统计题目(材料题)
（2）求连通分量的个数
给定一个包含 n 个节点（编号 0 到 n-1）的无向图，以及若干条边 edges。请使用并查集（Union-Find）计算图中连通分量的个数。要求：使用路径压缩 + 按秩合并；最终返回连通分量数量。
01 def count_components(n, edges):
02 parent = ①
03
04 rank = [0] * n
05 def find(x):
06 if parent[x] != x:
07 parent[x] = ②
08 return parent[x]
09 def union(x, y):
10 rx, ry = find(x), find(y)
11 if rx != ry:
12 if rank[rx] < rank[ry]:
13 ③
14 elif rank[rx] > rank[ry]:
15 ④
16 else:
17 parent[ry] = rx
18 rank[rx] += 1
19 for u, v in edges:
20 union(u, v)
21 roots = set()
22 for i in range(n):
23 roots.add(find(i))
24 return ⑤
||
关注我们
