并查集的演进：传统、种类与带权

前面几节维护的是区间。现在换个问题：不断有人告诉我们“两个人是一伙的”，还要随时问另两个人是不是一伙，怎么办？

这一讲沿着一条线往上加东西：先知道是不是一伙，再知道同一边还是对立面，最后知道两个人具体差多少。

一、传统并查集 (Standard Disjoint-Set)

1. 核心定义

传统并查集用于维护无向图中的连通块。它只能回答两个节点是否处于同一个集合中，同一集合里的人可以互相找到共同的代表。

通俗理解： “找祖宗”。朋友的朋友就是朋友，只要同属一个祖先，就是一家人。

2. 重要性质

路径压缩： 在查询过程中，将访问过的所有节点直接连接到根节点上。就像下次办事不用层层转达，直接找总负责人。
时间复杂度： 路径压缩再配合按大小合并（小集合挂到大集合），单次操作的均摊时间复杂度为 $O(\alpha(N))$ ，其中 $\alpha$ 为阿克曼函数的反函数，在竞赛数据范围内可视为极小的常数。

3. 求解算法与模板：P3367

洛谷 P3367【模板】并查集的操作 1 合并，操作 2 询问并输出 Y/N。当前题目 n 可到 200000，数组别只开 100005。

思路： 用 fa 数组记录每个节点的父节点。利用 init 函数初始自成一派。合并时将一棵树的根指向另一棵树的根。

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 200005;
int n, m, fa[N], sz[N];

void init(int n) {
    for (int i = 1; i <= n; i++){
        fa[i] = i;
        sz[i] = 1;
    }
}

int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

void merge(int x, int y) {
    x=find(x),y=find(y);
    if(x==y) return;
    if(sz[x]>sz[y]) swap(x,y);
    fa[x]=y;
    sz[y]+=sz[x];
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    init(n); // 初始化
    
    for (int i = 1; i <= m; i++) {
        int op, u, v;
        cin >> op >> u >> v;
        if (op == 1) merge(u, v);
        else cout << (find(u) == find(v) ? "Y\n" : "N\n");
    }
    return 0;
}

二、种类并查集 / 扩展域 (Extended Domain)

1. 核心定义

如果只分两个阵营，“敌人的敌人”就该站在同一边。普通并查集只记得谁和谁一伙，怎么顺便记住对立面？把每个人多开一个“对面”的编号，就能把这些关系也转成合并。

通俗理解： 开辟“平行宇宙”。节点 $x$ 在本我宇宙代表“他在阵营A”，在反我宇宙代表“他在阵营B”。把他们锁死，推导就自动完成了。

2. 重要性质

空间翻倍： 如果有 $K$ 种互斥状态，数组需开辟 $K \times N$ 的大小。
绑定关系： merge(u,v) 是把两个状态归成同一类，不是画一条单向箭头。敌对时绑定 u 和 v+n，同时绑定 v 和 u+n。
自动推导： 合并 $A$ 与 $B$ 的敌人域、合并 $B$ 与 $C$ 的敌人域后，底层的传递性会自动使 $A$ 和 $C$ 的本我域连通。

3. 求解算法与模板 (以二分图/敌对关系为例)

比如 A 与 B 敌对、B 与 C 敌对，合并后 A 与 C 会落在同一边。若又说 A 与 C 敌对，就撞上矛盾了。

下面是课堂模型，不绑定某道题的格式：输入 n、m 和 m 对敌对关系；能分成两边输出 OK，有矛盾输出 Conflict。

思路： 数组开两倍。 $1 \sim n$ 代表本我， $n+1 \sim 2n$ 代表反我（敌人）。若 $u, v$ 是敌人，则将 $u$ 连向 $v$ 的反我，将 $v$ 连向 $u$ 的反我。

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 400005; // 支持 n<=200000，扩展域开两倍
int n, m, fa[N], sz[N];

void init(int n) {
    for (int i = 1; i <= n; i++){
        fa[i] = i;
        sz[i] = 1;
    }
}

int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

void merge(int x, int y) {
    x=find(x),y=find(y);
    if(x==y) return;
    if(sz[x]>sz[y]) swap(x,y);
    fa[x]=y;
    sz[y]+=sz[x];
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    init(n * 2); // 初始化扩展域
    
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v; // u 和 v 是敌人
        
        // 冲突检测：如果发现 u 和 v 已经是朋友，则产生矛盾
        if (find(u) == find(v)) {
            cout << "Conflict\n";
            return 0;
        }
        
        // 逻辑绑定：u的敌人是v，v的敌人是u
        merge(u, v + n);
        merge(v, u + n);
    }
    cout << "OK\n";
    return 0;
}

三、带权并查集 (Weighted Disjoint-Set)

1. 核心定义

当不仅需要知道两点是否同属一个集合，还需要确切知道两点之间的相对距离、分数差或特定状态时，需要在并查集的边上赋予权值，利用空间向量运算来维护这些定量关系。

通俗理解： “树上向量加法”。边不仅代表“连通”，还带有方向和长度。顺着箭头走相加，逆着箭头走相减。

2. 重要性质

先把方向说清楚： 设 pot[x] 是 x 的分值，d[x]=pot[fa[x]]-pot[x]，也就是“父亲比我多多少”。pot 只用来帮助推导，不需要真的存出来。
路径压缩 (Find)： 满足向量加法。 $x$ 到总根的距离 = $x$ 到原父的距离 + 原父到总根的距离。
集合合并 (Merge)： 已知 pot[y]-pot[x]=w，若把 x 的根挂到 y 的根，新的边权是 $d[rx]=d[y]-d[x]+w$ 。

3. 先手算，再写模板

假设父亲比 x 多 3 分，总根又比父亲多 5 分。路径压缩后 x 直接连到总根，边上就应记 8。换了父亲，但相对分差不能跟着丢。

合并时也是算差值。已知 y 比 x 多 w，压缩后 d[x] 是根 rx 比 x 多多少，d[y] 是根 ry 比 y 多多少。沿着 rx → x → y → ry 算：先减 d[x]，加 w，再加 d[y]，就得到根 rx 挂到 ry 时要记的值。

如果两个人已经同根，不要再挂一次。此时 y 比 x 多的是 d[x]-d[y]，和新给的 w 对不上，就说明新关系矛盾。比如已知 B 比 A 多 3、C 比 B 多 5，那么 C 比 A 应该多 8；再告诉你差 9，就不能照单全收。

下面的课堂程序输入 n、m，支持两种操作：

1 u v w：加入“v 比 u 多 w”。不矛盾输出 OK；矛盾输出 Conflict，这条关系不加入。
2 u v：查询 v 比 u 多多少；关系还没连起来，输出 UNKNOWN。

分差可为负数，用 long long 存。思路： 在传统的 find() 函数中加入回溯时的累加逻辑；在 merge() 函数中手动获取根节点以严格套用闭环推导公式。

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 200005;
int n, m, fa[N], sz[N], d[N]; // d[i]=pot[fa[i]]-pot[i]，父亲比 i 多多少

void init(int n) {
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
        d[i] = 0;
        sz[i] = 1;
    }
}

int find(int x) {
    if (fa[x] == x) return x;
    int root = find(fa[x]);    // 先递归算好父节点到根的距离
    d[x] += d[fa[x]];          // 向量相加：当前到根 = 当前到父 + 父到根
    return fa[x] = root;
}

// 已知 pot[y]-pot[x]=w，返回这条关系是否可以接受
bool merge(int x, int y, int w) {
    int rx=find(x),ry=find(y);
    if(rx==ry) return d[x]-d[y]==w;
    if(sz[rx]<=sz[ry]){
        fa[rx]=ry;
        d[rx]=d[y]-d[x]+w;
        sz[ry]+=sz[rx];
    }else{
        fa[ry]=rx;
        d[ry]=d[x]-d[y]-w; // 反过来挂，差值也反过来
        sz[rx]+=sz[ry];
    }
    return true;
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    init(n);
    
    for (int i = 1; i <= m; i++) {
        int op,u,v,w;
        cin>>op>>u>>v;
        if(op==1){
            cin>>w;
            cout<<(merge(u,v,w)?"OK\n":"Conflict\n");
        }else{
            int ru=find(u),rv=find(v);
            if(ru!=rv) cout<<"UNKNOWN\n";
            else cout<<d[u]-d[v]<<"\n";
        }
    }
    return 0;
}

并查集的三种演化对比

4. 带权并查集的模意义进阶：处理环状关系

有些关系不是简单的数值累加，而是会“绕圈”的。比如经典的三物种食物链：A 吃 B，B 吃 C，C 吃 A。这构成了一个大小为 3 的环。

核心思路： 把关系变成模意义下的距离。设 d[x] 表示 x 到根节点的“相对代差”。规定：

d[x] % 3 == 0：与根节点同类
d[x] % 3 == 1：被根节点吃
d[x] % 3 == 2：吃根节点（具体谁吃谁看题目设定，只要全局统一即可）

推导与实现要点： 所有的加减运算全带上 % 3。

路径压缩时：d[x] = (d[x] + d[fa[x]]) % 3
合并与检测时：因为涉及减法，C++ 中的取模对负数保留负号，所以在算出的差值上要加上模数再取模以确保为正。比如检查新给定的相对关系 $w$ 时，计算 (d[x] - d[y] + 3) % 3 == w。这就把原本错综复杂的环形逻辑判断，直接降维成了极其简单的模加法。

四、离线思维：逆序加边处理“删边”

1. 痛点：并查集只会合并，不会拆解

并查集的核心优势是路径压缩。但路径压缩把树的原始结构“拍扁”了：原来通过好几条边连起来的节点，现在直接挂到了总根上。这就导致一个致命问题：如果题目要求“删除一条边”，我们根本不知道怎么把拍扁的树恢复原样。

2. 破局：时光倒流（离线逆向处理）

既然正着删边做不到，那我们就倒着加边。前提是题目只有“给定初始图、删除边、查询连通性”这三种情况，不包含混合的动态加边。我们可以“未卜先知”，把所有操作先读完存下来（这就是“离线”）。

推导步骤：

读入所有的初始边和所有的删边、查询操作。
找出那些从头到尾都没被删除过的边，先把它们用并查集连起来，构成“最终被摧毁后的废墟状态”。
从最后一个操作开始，往前倒推：
- 如果遇到“查询”，就用当前并查集的状态得出答案，存进答案数组。
- 如果遇到“删除某条边”，在时光倒流的视角下，这其实是“把这条边加回去”！直接合并即可。
最后把存好的答案逆序输出。

小例子： 节点 1-2-3 连通。操作 1：查 1,3 是否连通（是）操作 2：删 1-2 的边操作 3：查 1,3 是否连通（否）

倒推视角：最终废墟：只有 2-3 连通（假设这是唯一没被删的边）。倒着遇到操作 3（查 1,3）：查废墟，不连通。记录“否”。倒着遇到操作 2（删 1-2）：倒推就是立刻连上 1-2。倒着遇到操作 1（查 1,3）：查当前并查集，1,2,3 已连通。记录“是”。逆序输出：是、否。完美解决！

3. 完整代码演示

下面给出一个自拟练习题的完整结构代码。 输入格式： 第一行 n, m, q（n个点，m条初始无向边，q个操作， $1\le n\le 10^5$ ）。接下来 m 行是初始无向边。接下来 q 行，1 u v 代表删边，2 u v 代表查询是否连通。保证初始图无重边，每条边至多删一次，删的边一定在初始图中存在。 样例：

对应输出：

Yes
No

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 100005;
int n, m, q, fa[N];

struct Query {
    int op, u, v;
};

void init(int n) {
    for (int i = 1; i <= n; i++) fa[i] = i;
}

int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

void merge(int x, int y) {
    x = find(x), y = find(y);
    if (x != y) fa[x] = y;
}

void solve() {
    cin >> n >> m >> q;
    init(n);
    
    // 记录初始边，并统计每条边是否被删
    map<pair<int,int>, int> del_edges;
    vector<pair<int,int>> edges(m);
    for(int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        if (u > v) swap(u, v);
        edges[i] = {u, v};
    }
    
    vector<Query> qs(q);
    for(int i = 0; i < q; i++) {
        cin >> qs[i].op >> qs[i].u >> qs[i].v;
        if (qs[i].op == 1) {
            int u = qs[i].u, v = qs[i].v;
            if (u > v) swap(u, v);
            del_edges[{u, v}] = 1; // 标记被删除
        }
    }
    
    // 第一步：将直到最后都没被彻底删掉的边合并，构建废墟
    for(auto& e : edges) {
        if(!del_edges[e]) {
            merge(e.first, e.second);
        }
    }
    
    // 第二步：时光倒流，逆序处理询问
    vector<string> ans;
    for(int i = q - 1; i >= 0; i--) {
        int u = qs[i].u, v = qs[i].v;
        if (qs[i].op == 2) {
            ans.push_back(find(u) == find(v) ? "Yes" : "No");
        } else {
            // 删边操作，倒退时变成加边
            merge(u, v);
        }
    }
    
    // 第三步：再把倒退得到的答案逆序输出
    for(int i = ans.size() - 1; i >= 0; i--) {
        cout << ans[i] << '\n';
    }
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    solve();
    return 0;
}

五、选学：可回滚并查集 (Undoable DSU)

前面的“时光倒流”有个前提：题目只有初始加边和后续删边，且能提前把所有的询问读完（离线）。如果撤销顺序是“后加先撤”，比如在深度优先搜索（DFS）中往下走时加边，回溯时撤销刚才的合并，怎么办？这就可以用到“可回滚并查集”。它只能按栈序撤销，不能直接拿来处理任意顺序的在线删边。

1. 为什么坚决不用路径压缩？

在普通并查集里，路径压缩是最大的功臣，但在可回滚并查集里，它是致命的累赘！因为路径压缩一次会把一长串节点的 fa 全部直连到根，把树形结构破坏殆尽。如果你想撤销这一次合并，你得把那一串节点的 fa 全部原样复原，时空消耗都是 $O(N)$ ，得不偿失。

解决方案：只用“按大小合并”（或按秩合并）。 绝不压缩路径！我们把小集合直接挂到大集合下面，这样能通过树的平衡性保证树的深度永远不超过 $\log N$ 。查询的时候一步步往上爬，最坏也是 $O(\log N)$ ，速度依然非常快。而且最关键的是：每次合并，仅仅只改变了两个数值（一个 fa，一个 sz）！

2. 回滚逻辑：小本本记录法

既然每次 merge 仅仅是修改了子节点的 fa 和父节点的 sz，那我们就拿个“小本本”（通常用 stack 栈）把这次修改前的原始状态记下来。要撤销（回溯）时，从栈顶拿出当时的记录，把数据覆盖回去，瞬间搞定。

3. 代码实现要点

下面的代码展示了如何在需要回溯的场景中优雅地撤销并查集状态。通过栈保证了“后进先出”的完美对称。

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 100005;
int fa[N], sz[N];

// 记录历史的小本本：存被修改的节点 x，以及它被覆盖前的 fa 和 sz
struct History {
    int x, old_fa, old_sz;
};
stack<History> st;

void init(int n) {
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
        sz[i] = 1;
    }
}

// 绝对不能有路径压缩！只能一步一步爬到根
int find(int x) {
    while (x != fa[x]) x = fa[x];
    return x;
}

// 返回这次是否真的发生了实质性合并
bool merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return false; 
    
    // 启发式合并：小树挂大树
    if (sz[x] > sz[y]) swap(x, y);
    
    // 核心：在正式修改前，把将被波及的 x 和 y 的原状态压入栈中
    st.push({x, fa[x], sz[x]});
    st.push({y, fa[y], sz[y]});
    
    fa[x] = y;
    sz[y] += sz[x];
    return true;
}

// 撤销最近的一次有效合并
void undo() {
    if(st.empty()) return;
    // 出栈顺序必须与入栈顺序严格相反（后进先出）
    History hy = st.top(); st.pop();
    fa[hy.x] = hy.old_fa;
    sz[hy.x] = hy.old_sz;
    
    History hx = st.top(); st.pop();
    fa[hx.x] = hx.old_fa;
    sz[hx.x] = hx.old_sz;
}

void solve() {
    init(4);
    merge(1, 2); // 连通 1-2
    
    bool merged = merge(2, 3); // 连通 2-3
    cout << (find(1) == find(3) ? "1-3 connected" : "1-3 disjoint") << '\n';
    
    // 模拟 DFS 回溯，撤销上一步操作
    if (merged) undo(); 
    cout << (find(1) == find(3) ? "1-3 connected" : "1-3 disjoint") << '\n';
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    solve();
    return 0;
}

六、三种并查集，其实是一条线

问题多问了什么	用什么记录	先想清楚什么
是不是一伙	`fa`	是否有同一个根
同边还是对立面	两倍编号	哪两种状态应该绑定
具体差多少	`fa` 和 `d`	d 的方向，以及路径压缩时怎么相加

普通并查集会在 Kruskal 最小生成树里继续出现。扩展域解决阵营关系，带权并查集则把“有关系”升级成“知道关系的数值”。

别把 fa 当成原图中的边：它只是帮我们管理集合的。普通并查集擅长合并，不直接支持随意拆开一个集合。

七、课后训练：关系多一层，记录也多一层

P1892 团伙：朋友、敌人的敌人分别怎么合？统计时只看真实人员的集合。
P1525 关押罪犯：按怨气从大到小处理，先把最不能在一起的人分开；第一次出现矛盾时，答案就浮出来了。
P1196 银河英雄传说：把整列接到另一列后面，维护队列大小和到根的距离，最后想清楚“两艘之间”为什么还要减一。
P2024 食物链：关系变成三类循环，可以用三倍扩展域，也可以让带权关系对 $3$ 取模；先判假话，再决定是否合并。
P1197 星球大战：逆序恢复的是点，不是第四节的删边。恢复一个点后，再把它与当前存在的邻点合并；留意原题从 $0$ 编号，还要输出初始连通块数。