并查集进阶

维护连通块信息

核心

将每个并查集（即连通块）的信息存储在根节点上，并在合并时更新。

常见

假设合并p[rx] = ry;

• 连通块大小 sz[ry] += sz[rx];

• 块内最大值（最小值同理） mx[ry] = max(mx[ry], mx[rx]);

• 块内和 sum[ry] += sum[rx]; ……

带权并查集

核心

在普通并查集的基础上增加权值数组，记录每个节点到父节点（或根节点）的权值。

作用

处理一些需要维护元素间关系的场景，如距离、差值、互斥等。

操作

$a\rightarrow b$: a到b的权值 $p$: 父节点 parent $r$: 根节点 root $w$: 权值 weight

初始化

// p: 父节点数组，w: 权值数组
vector<int> p(n), w(n, 0);
// 父节点初始化为自己，权值初始化为0
for(int i = 0; i < n; i++) p[i] = i; 

---

Find

• 更新逻辑

1. 新父节点 = 根节点 $r$ $\therefore$更新$w_x$为 $x\rightarrow r$ 权值
2. 原$w_x$为 $x\rightarrow p$ 权值
3. 递归栈结构，保证$w_{p_x}$已更新为$p \rightarrow r$ 权值
4. 权值 $x\rightarrow r = x\rightarrow p\rightarrow r$ $\therefore$ $w_x = w_x + w_{p_x}$

• 更新顺序

1. 先更新权值，此时父节点还是原来的父节点
2. 后路径压缩，父节点更新为根节点

int find(int x){
    if(p[x] != x){
        // 找到根节点
        int t = find(p[x]);
        // 先更新权值（保证父节点有效）
        w[x] += w[p[x]]; 
        // 后路径压缩
        p[x] = t; 
    }
    return p[x];
}

---

Union

更新逻辑

$w_0$ 为 $y\rightarrow x$ 权值 将$r_y$父节点指向$r_x$ $w_{r_y}$ 更新为 $r_y \rightarrow r_x$ 权值

1. $y\rightarrow r_x = y\rightarrow r_y \rightarrow r_x$ = $w_y + w_{r_y}$
2. $y\rightarrow r_x = y\rightarrow x\rightarrow r_x$ = $w_x + w_0$ $\therefore w_y + w_{r_y} = w_x + w_0$ $\therefore w_{r_y} = w_x - w_y + w_0$

// w0为y到x的权值
bool unite(int x, int y, int w0){
    // 找到根节点
    int rx = find(x);
    int ry = find(y);
    // 已在同一集合，检查权值合法
    if(rx == ry) return w[y] - w[x] == w0;
    // 不在同一集合，先合并集合
    // 这里也可以加入优化，如按秩合并
    p[ry] = rx;
    // 更新权值
    w[ry] = w[x] - w[y] + w0;
    return true;
}

补充： 这里只演示了加性权值的情况，实际上权值迁移可以是乘、异或等任意运算。

离线并查集

核心

• 先记录所有操作
• 将分离转换为逆向合并
• 或重排序规避分离操作

作用

处理需要动态修改关系、分离集合的场景，如动态连通性、动态图等。

扩展域并查集

核心

• 给每个状态分配一个为 $n$ 的域
• 元素 $x$ 的状态 $i$ 为 $x + n \cdot i$
• 合并操作时，将两个元素的相同状态域合并

$n$ 一般取为元素个数

本质

设有 $n$ 个元素，每个元素有 $m$ 个状态维度

• 需要维护 $m$ 个集合，每个集合中元素的状态全部相同
• 这 $m$ 个集合称为 $m$ 个域
• $+ n$ 是一种状态编码，通过 $+ n \cdot i$ 访问状态 $i$
• 也存在其他编码方式，如维护一个状态数组、或用权值异或传导（仅支持2维）

作用

处理维护元素互斥状态的场景，如组合、染色等。

例题

洛谷P1196 银河英雄传说 洛谷P1525 关押罪犯 洛谷P1197 星球大战 洛谷P2024 食物链