UnionFind检测连通性比DFS/BFS更合适，因其均摊时间复杂度接近O(α(n))，远优于每次重跑DFS/BFS的O(V+E)，且专为动态加边和高频连通查询优化，但不支持删边或求路径。
为什么用 UnionFind 检测连通性比 DFS/BFS 更合适？
当图的边是动态添加（比如在线加边、合并子图），或需要高频查询「两个节点是否连通」时，UnionFind 的均摊时间复杂度接近 O(α(n))，远优于每次重跑 DFS/BFS 的 O(V+E)。它不关心路径，只回答「是否同属一个连通分量」——这正是连通性检测的本质需求。
注意：UnionFind 无法获取具体路径、不能处理带权图的最短连通性、也不支持删边。如果图结构固定且只需一次判断，DFS/BFS 反而更轻量。
基础实现必须带路径压缩和按秩合并
不加优化的朴素并查集在链式结构下会退化成 O(n) 单次操作，实际中几乎不可用。以下是最小可用版本的关键点：
-
find必须递归或循环做路径压缩：把沿途所有节点父指针直接指向根 -
union必须比较两棵树的rank（或size），小树挂到大树下，避免深度激增 - 初始化时每个节点自成一集，
parent[i] = i，rank[i] = 0
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
<pre class="brush:php;toolbar:false;">def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # 路径压缩
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return
if self.rank[px] <p></p>检测无向图连通性：别漏掉孤立点
给定边列表 edges = [(0,1), (1,2), (3,4)]，节点范围可能是 0 到 n-1，但并非所有编号都一定出现在边里。常见错误是只遍历 edges 中出现的节点，导致孤立点（如只有边 (0,1) 但总节点数为 5）被忽略。
Python Sdk
下载
inference.sh 的 Python SDK：运行 AI 应用、构建智能体，并集成 150 多个模型。包名：inferencesh (pip install inferencesh)。支持同步/异步……
正确做法：
- 明确传入总节点数
n（通常由题干给出，或从边中推断max(max(u,v) for u,v in edges) + 1） - 初始化
UnionFind(n)，再逐条union(u, v) - 最后统计不同根的数量：
len(set(uf.find(i) for i in range(n))) == 1
若只要判断是否连通，可提前终止：当 union 次数达到 n-1 且全部成功合并，说明已成一棵树（但需注意重边）。
遇到「连通分量数量」或「最大连通块大小」怎么办？
UnionFind 原生不暴露分量信息，得额外维护。推荐在初始化时加 self.size = [1] * n，并在 union 时更新：
self.size[root]
Python免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 Python 的核心概念和高级技巧！
