7.1 并查集：门派联盟与路径压缩

7.1 并查集：门派联盟与路径压缩

本节摘要：并查集（DSU）维护"不相交的集合"，只招两式：find 查元素属于哪个门派、union 合并两个门派。配路径压缩与按秩合并，单次操作均摊近乎常数。它是 Kruskal 判环（4.4 节）的正式修炼、连通分量的账房先生、动态等价关系的标准兵器。本节实现双优化版本并复现"不压缩时长链、压缩后近乎扁平"的对比。

两个门派的事，一棵树来说

把每个集合想成一个门派：掌门（根节点）是唯一标识，弟子（子节点）指向师父。查门派 find(x)：从 x 一路向上问到根；合并门派 union(a,b)：让一个掌门拜另一个掌门为师。两式之外不需要更多——不能按值查找、不能有序遍历，换来的是合并与查询都极快。

朴素实现有个隐患：union 时随手把 a 的根挂到 b 的根下面，运气不好会长成一条长链，find 从链底问到链顶，退化成 O(n)。两式优化专门治这个：

• 路径压缩：find 的回程路上，把沿途所有节点直接改挂到根下面——第一次问路辛苦，之后人人一步到位；
• 按秩合并：合并时矮树挂高树下，别让大树给小树当弟子，树高不会无谓增长。

路径压缩：一次问路，全员直达

# 并查集：路径压缩 + 按秩合并，步数全程计数
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))     # 起初人人自成一派
        self.rank = [0] * n              # 树高估计
        self.steps = 0                   # 记账：find 走了几步

    def find(self, x, compress=True):
        root = x
        while self.parent[root] != root:     # 先找到掌门（steps 只数跳转）
            root = self.parent[root]
            self.steps += 1
        if compress:
            while self.parent[x] != root:    # 回程：沿途直挂掌门
                self.parent[x], x = root, self.parent[x]
                self.steps += 1
        return root

    def union(self, a, b, by_rank=True, compress=True):
        ra, rb = self.find(a, compress), self.find(b, compress)
        if ra == rb:
            return False                 # 同门：合并失败（判环信号）
        if by_rank and self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra               # 矮树挂高树
        self.parent[rb] = ra              # rb 门派并入 ra
        if by_rank and self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True

# 造一条链：0←1←2←3←4←5（5 挂 4，4 挂 3，……）
def chain_dsu(n, compress):
    d = DSU(n)
    for i in range(n - 1, 0, -1):        # 逐级认师，人为造出长链
        d.parent[i] = i - 1
    return d

d1 = chain_dsu(6, False)
d1.steps = 0
d1.find(5, compress=False)
print("不压缩：查一次掌门走", d1.steps, "步")
# 输出：不压缩：查一次掌门走 5 步

d2 = chain_dsu(6, True)
d2.steps = 0
d2.find(5, compress=True)                # 第一次辛苦
d2.steps = 0
d2.find(4, compress=True)                # 之后任意成员一步直达
print("压缩后再查：", d2.steps, "步")
# 输出：压缩后再查： 1 步
​

两式合璧后，单次操作的均摊复杂度是真解的极小函数（反阿克曼级别），在一切现实规模下当作常数使用。工程与竞赛里"并查集近乎 O(1)"的说法，指的就是这套组合。

战场：连通分量、判环、Kruskal

# 并查集三连：连通分量计数、无向图判环、Kruskal 主体
edges = [(0, 1), (1, 2), (3, 4), (4, 5)]
n = 6
d = DSU(n)
for u, v in edges:
    d.union(u, v)
groups = len({d.find(i) for i in range(n)})
print("连通分量数：", groups)
# 输出：连通分量数： 2（0-1-2 一派，3-4-5 一派）

d2 = DSU(n)
cycle = False
for u, v in edges + [(2, 0)]:            # 加一条回边 2-0
    if not d2.union(u, v):               # 同门再连边 → 环
        cycle = True
print("加回边后判环：", cycle)
# 输出：加回边后判环： True
# Kruskal（4.4 节）正是靠这一信号拒绝成环边——union 返回 False 即跳过
​

并查集的适用面比"图"更宽：等价关系动态合并（朋友圈合并、域名归并）、离线处理删边（反向加边）、判断冲突（分配房间问题：敌人关系约束下的安置）都能套用。识别信号：只问"这两个点是否同组"、只做"把两组合并"，别无他求。

⚠️ 常见坑：只做路径压缩不做按秩合并（或反之）在特定输入下仍会退化出深树；两式同开才有那个"近乎常数"的保证。另一个坑：find 递归写在千层深链上可能爆栈（1.3 节的老朋友），上迭代版稳。

💡 关键直觉：路径压缩是"记账换查询"的又一次胜利（前缀和、记忆化同宗）：第一次多走几步，把沿途信息写回结构，此后人人一步。数据结构的进化史，半部是空间换时间史。

走火入魔：需求不匹配的硬上

并查集不能做的事也要心里有数：不能拆分（union 之后无法撤销，删边问题只能离线倒着加边）、不能按组遍历成员（只认掌门不认名单，要名单得额外挂链表）、不维护序（组内无顺序，范围查询免谈）。带着这三样需求来的，请右转平衡树或线段树（下一节）。

本节要点回顾

• 并查集两式：find 问掌门、union 并门派；只服务"同组判定与合并"，换取近乎常数的均摊复杂度；
• 路径压缩回程直挂、按秩合并矮挂高，双开才有理论保证；链上实测：压缩前五步、压缩后一步；
• 判环信号即 union 返回 False——Kruskal 拒绝成环边、无向图环检测都是它；
• 三大不能：不能拆分、不能点名、不能有序；需求越界就换兵器；
• 又见"空间换时间"：结构与算法的进化半部是记账史。

分组的事交给了并查集；区间的事——边改边查的硬需求——轮到线段树与树状数组出场。