并查集应用（扩展域 / 带权 / 可撤销 / Kruskal 重构树）

What · 是什么

并查集（Disjoint Set Union / DSU）维护集合合并与『是否同一集合』查询。其应用远超基础连通性：① 扩展域并查集：把『关系』编码进多个维度（如食物链的三种动物关系，用 3 个域表达捕食/天敌/同类）；② 带权并查集：每个节点到父节点的权值（距离），路径压缩时同步累加，查询两节点间关系（银河英雄传说求两列间距）；③ 可撤销并查集：不用路径压缩、只按秩合并，记录操作历史支持回退（配合离线/时间线题目）；④ Kruskal 重构树：在 Kruskal 加边时新建代表边权的节点作为子树根，得到一棵满足『子树内任意两点连通时间 ≤ 根权值』的重构树，把『最小瓶颈/最早连通时间』问题转成树上倍增；⑤ 其他应用：每个边只覆盖一次的树上并查集（跳路径缩点）、按连通块合并方向维护统计等。

Why · 为什么

How · 实现

伪代码

DSU:
    parent[], rank[]/size[]
    find(x): 路径压缩（带权时累加 dist）
    union(x,y): 按秩合并

# 扩展域（3 域食物链）：节点数 3n，域 0/1/2 = 同类/猎物/天敌
union((x,0),(y,1)); union((x,1),(y,2)); union((x,2),(y,0))

# Kruskal 重构树
for 边 (u,v,w) in 按 w 升序:
    if find(u)!=find(v):
        node = new(w); parent[node]=node
        parent[find(u)]=node; parent[find(v)]=node   # 连为儿子
query(u,v): LCA 权值

# 可撤销：
# union 时 push (x,y,rank) 到栈；rollback 时反向恢复

Python 实现

class DSU:
    def __init__(self, n):
        self.par = list(range(n))
        self.sz = [1] * n
    def find(self, x):
        while self.par[x] != x:
            self.par[x] = self.par[self.par[x]]
            x = self.par[x]
        return x
    def union(self, a, b):
        a, b = self.find(a), self.find(b)
        if a == b:
            return False
        if self.sz[a] < self.sz[b]:
            a, b = b, a
        self.par[b] = a
        self.sz[a] += self.sz[b]
        return True

class RollbackDSU:
    """可撤销并查集：按秩合并 + 历史栈"""
    def __init__(self, n):
        self.par = list(range(n))
        self.depth = [1] * n
        self.hist = []
    def find(self, x):
        while self.par[x] != x:
            x = self.par[x]
        return x
    def union(self, a, b):
        a, b = self.find(a), self.find(b)
        if a == b:
            self.hist.append(None)
            return False
        if self.depth[a] < self.depth[b]:
            a, b = b, a
        self.hist.append((b, a, self.depth[a]))
        self.par[b] = a
        if self.depth[a] == self.depth[b]:
            self.depth[a] += 1
        return True
    def rollback(self):
        rec = self.hist.pop()
        if rec is None:
            return
        b, a, da = rec
        self.par[b] = b
        self.depth[a] = da

class WeightedDSU:
    """带权并查集：dist[x] 为 x 到根的距离（相对关系）"""
    def __init__(self, n):
        self.par = list(range(n))
        self.dist = [0] * n
    def find(self, x):
        if self.par[x] == x:
            return x
        r = self.find(self.par[x])
        self.dist[x] += self.dist[self.par[x]]
        self.par[x] = r
        return r
    def union(self, x, y, d):
        """使 dist[x] - dist[y] == d（d 可为负）"""
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return self.dist[x] - self.dist[y] == d
        self.par[rx] = ry
        self.dist[rx] = d + self.dist[y] - self.dist[x]
        return True
    def relation(self, x, y):
        self.find(x); self.find(y)  # 先压缩路径，dist 才准确
        return self.dist[x] - self.dist[y]

if __name__ == '__main__':
    # 基础连通性
    d = DSU(5)
    d.union(0, 1); d.union(1, 2)
    assert d.find(0) == d.find(2) and d.find(0) != d.find(3)
    print('DSU OK')
    # 带权：x-y=2, y-z=3 => x-z=5
    w = WeightedDSU(4)
    assert w.union(0, 1, 2)
    assert w.union(1, 2, 3)
    assert w.relation(0, 2) == 5
    assert w.union(0, 2, 5) is True
    assert w.union(0, 2, 6) is False
    print('WeightedDSU OK')
    # 可撤销
    r = RollbackDSU(4)
    r.union(0, 1); r.union(2, 3)
    assert r.find(0) == r.find(1)
    r.rollback()  # 撤销 (2,3)
    assert r.find(2) != r.find(3)
    assert r.find(0) == r.find(1)
    print('RollbackDSU OK')

易错点

• 可撤销并查集必须只按秩合并、不路径压缩，否则历史栈失效
• 带权并查集 union 的 dist 计算方向容易错，建议统一『dist[x]-dist[y]=d』并画图推导
• 扩展域节点数 = n×域数，数组开小是典型 RE/WA
• Kruskal 重构树查询是『两点 LCA』而不是 min(dist)，注意与倍增祖先权值比较的方向
• find 递归过深（n≥10^5 且未路径压缩）会爆栈，用迭代实现

例题

信源

• OI Wiki✓ https://raw.githubusercontent.com/OI-wiki/OI-wiki/master/docs/topic/dsu-app.md
• CP-Algorithms✓ https://cp-algorithms.com/data_structures/disjoint_set_union.html