什么是并查集？

实现一个共用的群组之集合的类，通过群主表示不同的群组，当且仅当群主是自己表示孤立节点或者群主节点，每个人都有一个主，修改了主只需要修改一个，在查的时候按照主的主来寻找最终的主，最开始每个人的主是自己。

核心操作

Find：查找元素所属集合的代表元（根节点）
Union：合并两个元素所在的集合

想象你有一堆人（节点），他们之间会互相认识（连接）。并查集就是用来：

快速判断两个人是否互相认识（直接或间接）
让两个不认识的人变成认识（把他们的朋友圈合并）

生活中的例子

假设班上有5个同学：

小明、小红、小刚、小丽、小强

初始状态：每个人只认识自己

第一步：建立朋友圈

小明和小红成为朋友 → 他们现在是一个朋友圈
小刚和小丽成为朋友 → 另一个朋友圈
小强自己一个人 → 单独的朋友圈

现在朋友圈情况：

朋友圈1：小明、小红
朋友圈2：小刚、小丽
朋友圈3：小强

第二步：朋友的朋友

小红认识了小刚 → 现在小红的朋友圈和小刚的朋友圈合并

现在朋友圈情况：

大朋友圈：小明、小红、小刚、小丽
单独朋友：小强

第三步：查询是否认识

小明认识小丽吗？ → 是的（通过小红和小刚）
小明认识小强吗？ → 不认识

代码实现（最简单版）

class FriendCircle:
    def __init__(self, n):
        self.parent = list(range(n))  # 初始每个人的上级是自己
    
    def find(self, x):
        # 找x的最终上级（朋友圈代表）
        while self.parent[x] != x:
            x = self.parent[x]
        return x
    
    def union(self, x, y):
        # 让x和y成为朋友（合并朋友圈）
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root != y_root:
            self.parent[y_root] = x_root
    
    def is_connected(self, x, y):
        # 判断x和y是否是朋友
        return self.find(x) == self.find(y)

# 使用示例
fc = FriendCircle(5)  # 5个人：0(小明),1(小红),2(小刚),3(小丽),4(小强)

# 建立朋友关系
fc.union(0, 1)  # 小明和小红成为朋友
fc.union(2, 3)  # 小刚和小丽成为朋友
fc.union(1, 2)  # 小红和小刚成为朋友

# 查询
print(fc.is_connected(0, 3))  # 输出True，小明认识小丽
print(fc.is_connected(0, 4))  # 输出False，小明不认识小强

关键点总结

**找上级(find)**：一直向上找，直到找到终极老大（朋友圈代表）
**交朋友(union)**：让两个人的终极老大变成同一个人
**查关系(is_connected)**：看两个人的终极老大是不是同一个人

典型应用

动态连通性问题
图的连通分量检测
最小生成树算法（Kruskal算法）
网络连接判断
图像处理中的像素连通区域

优缺点：只适合维护连通性，不适合删除

时间复杂度分析

并查集的效率取决于 路径压缩（Find优化） 和 按秩合并（Union优化）。

操作	普通并查集	路径压缩	路径压缩 + 按秩合并
初始化	O(N)	O(N)	O(N)
Find	O(N)	O(α(N))	O(α(N))
Union	O(N)	O(α(N))	O(α(N))

其中：

α(N) 是 反阿克曼函数，增长极其缓慢（对于任何实际应用的N，α(N) ≤ 5）。
因此，**优化后的并查集操作接近 O(1)**。

并查集 vs. 其他数据结构对比

操作	并查集	DFS/BFS	动态图（Link-Cut Tree）
查询连通性	✅ O(α(N))	✅ O(V+E)	✅ O(log N)
查询路径	❌ 不支持	✅ 支持	✅ 支持
动态加边	✅ 高效	❌ 每次O(V+E)	✅ 高效
动态删边	❌ 不支持	❌ 不支持	✅ 支持
查询集合大小	⚠️ 需额外维护	❌ 不适合	⚠️ 需额外维护
遍历集合元素	❌ 不高效	✅ 可以	✅ 可以

3. 什么时候避免使用并查集？

需要查询具体路径 → 用 DFS/BFS。
需要频繁删除边 → 用 动态图算法（如 Link-Cut Tree）。
需要实时查询集合大小或元素 → 用 哈希表 + 并查集扩展。
需要切分集合 → 用 离线处理或高级数据结构。