InoueMoby's Blog

前言

想象一群人在组队。开始时每个人单独一队。有人问：“你和那个人是一队的吗？“如果你们之间有一条”队友链”（你的队友的队友的……），那答案就是”是”。随着时间推移，队伍不断合并——两个队可能因为某个共同成员而合并成一个大队伍。

这就是并查集（Disjoint Set Union, DSU）要解决的问题：

合并（Union）：把两个组合并成一个
查询（Find）：两个人是否在同一个组？

并查集的代码只有十几行，但背后的优化思想——路径压缩和按秩合并——让它成为几乎 $O(1)$ 的数据结构。它是 Kruskal 最小生成树、连通性判断、等价类维护的核心工具。

问题的本质

连通性：图的隐含问题

在一个有 $N$ 个节点、 $M$ 条边的图上，“节点 $u$ 和 $v$ 是否连通”是一个基础问题。BFS/DFS 可以回答，但每次查询 $O(N+M)$ 太慢。如果边在动态添加，而且要随时查询连通性呢？

并查集巧妙地把”连通性”转化为”归属关系”：每个连通块选一个”代表”（根节点），两个节点连通当且仅当它们的代表相同。合并两个连通块，就是让一个代表服从另一个。

为什么路径压缩如此重要？

朴素实现中，find(x) 需要沿着 parent 指针一直走到根，最坏情况 $O(n)$ 。但如果我们顺路把路径上所有节点的 parent 直接指向根呢？下次查询就只需要 $O(1)$ 了。这叫路径压缩。

更惊人的是，结合按秩合并，并查集的单次操作均摊时间复杂度是 $O(\alpha(n))$ ，其中 $\alpha$ 是反阿克曼函数。对于所有实际可能的数据规模， $\alpha(n) \le 4$ 。所以实际上是常数时间。

理论 + 代码

基本实现

int parent[MAXN];

int find(int x) {
    if (parent[x] != x)
        parent[x] = find(parent[x]);  // ① 路径压缩：直接指向根
    return parent[x];
}

void unite(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx != ry) parent[rx] = ry;    // ② 把 x 的根挂到 y 的根下
}

逐行解析：

① 递归查找根节点。parent[x] = find(parent[x]) 是路径压缩的关键——递归返回时，把 $x$ 的 parent 直接设为根，下次查询就是 $O(1)$ 。
② 合并两个集合。让一个根认另一个根做”上级”。

按秩合并

朴素合并可能导致树退化成链。按秩合并的思想：始终把较矮的树挂到较高的树下面。

int rnk[MAXN];  // 树的高度（秩）

void unite(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx == ry) return;                 // ① 已经在同一集合
    if (rnk[rx] < rnk[ry]) parent[rx] = ry;      // ② 矮树挂高树
    else if (rnk[rx] > rnk[ry]) parent[ry] = rx;
    else { parent[ry] = rx; rnk[rx]++; }         // ③ 同高时任选，高度+1
}

模拟走一遍

初始 5 个节点各自为根。执行 unite(1,2), unite(3,4), unite(2,4)：

操作	parent 变化	说明
初始	[0,1,2,3,4,5]	每个节点的 parent 是自己
unite(1,2)	parent[1]=2	1 认 2 做上级
unite(3,4)	parent[3]=4	3 认 4 做上级
find(2)=2, find(4)=4	不变	各自的代表
unite(2,4)	parent[2]=4	2 的根挂到 4 下
find(1)	parent[1]=4	路径压缩！1 直接指向根 4

最终：{1,2} 和 {3,4} 合并成 {1,2,3,4}，5 独立。find(1)=find(2)=find(3)=find(4)=4。

例题

例题 1：TB A66 — Connect Query

题目： $N$ 个节点的图，初始无边。 $Q$ 个查询：

查询 1 1 u v：添加边 $(u, v)$

查询 2 2 u v： $u$ 和 $v$ 是否连通？输出 Yes 或 No

数据范围： $2 \le N, Q \le 10^5$

—— AtCoder Tessoku Book A66

分析：裸的并查集。添加边 = 合并，查询连通性 = 判断代表是否相同。

代码：

#include <cstdio>
using namespace std;

const int MAXN = 100006;
int parent[MAXN], rnk[MAXN];

int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]); // ① 路径压缩
    return parent[x];
}

void unite(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx == ry) return;
    if (rnk[rx] < rnk[ry]) parent[rx] = ry;          // ② 按秩合并
    else if (rnk[rx] > rnk[ry]) parent[ry] = rx;
    else { parent[ry] = rx; rnk[rx]++; }
}

int main() {
    int N, Q;
    scanf("%d%d", &N, &Q);
    for (int i = 1; i <= N; i++) { parent[i] = i; rnk[i] = 0; } // ③ 初始化
    while (Q--) {
        int t, u, v;
        scanf("%d%d%d", &t, &u, &v);
        if (t == 1) unite(u, v);                         // ④ 添加边
        else printf("%s\n", find(u) == find(v) ? "Yes" : "No"); // ⑤ 查询
    }
    return 0;
}

逐行解析：

① 路径压缩：递归查找根，同时把路径上所有节点直接指向根。
② 按秩合并：矮树挂高树，防止退化。
③ 初始化：每个节点自己是自己的 parent。
④ 查询 1 用 unite 合并两个节点所在的集合。
⑤ 查询 2 比较两个节点的根是否相同。

例题 2：ACL Practice A — Disjoint Set Union

题目： $N$ 个节点 0 条边的无向图。 $Q$ 个查询：

0 u v：添加边 $(u, v)$

1 u v： $u$ 和 $v$ 是否连通？输出 1 或 0

数据范围： $1 \le N, Q \le 2 \times 10^5$ ，节点编号 $0$ ~ $N-1$

—— AtCoder ACL Practice A

分析：和例题 1 几乎一样，区别是节点从 0 开始，输出 1/0 而不是 Yes/No。

代码：

#include <cstdio>
using namespace std;

const int MAXN = 200006;
int parent[MAXN], rnk[MAXN];

int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]);
    return parent[x];
}

void unite(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx == ry) return;
    if (rnk[rx] < rnk[ry]) parent[rx] = ry;
    else if (rnk[rx] > rnk[ry]) parent[ry] = rx;
    else { parent[ry] = rx; rnk[rx]++; }
}

int main() {
    int N, Q;
    scanf("%d%d", &N, &Q);
    for (int i = 0; i < N; i++) { parent[i] = i; rnk[i] = 0; } // ① 0-indexed
    while (Q--) {
        int t, u, v;
        scanf("%d%d%d", &t, &u, &v);
        if (t == 0) unite(u, v);                          // ② 添加边
        else printf("%d\n", find(u) == find(v) ? 1 : 0);  // ③ 输出 1/0
    }
    return 0;
}

逐行解析：

① 0-indexed 初始化。ACL Practice 的节点编号从 0 开始。
② 查询 0（t==0）= 添加边，用 unite 合并。
③ 查询 1（t==1）= 判断连通，比较 find 结果。输出 1 或 0，不是 Yes/No。

例题 3：T90 012 — Red Painting（★4）

题目： $H \times W$ 的网格，初始全白。 $Q$ 个查询：

1 r c：把格子 $(r,c)$ 涂红

2 ra ca rb cb：判断红色格子 $(ra,ca)$ 和 $(rb,cb)$ 是否通过红色格子上下左右相连

数据范围： $1 \le H, W \le 2000$ ， $1 \le Q \le 10^5$

—— AtCoder Typical 90 012

分析：这是并查集的二维应用。每涂红一个格子，检查它的上下左右邻居是否也是红色——如果是，就合并。查询时检查两个格子是否在同一连通块，且都是红色。

代码：

#include <cstdio>
using namespace std;

const int MAXN = 2001;
int parent[MAXN * MAXN], rnk2[MAXN * MAXN];
bool red[MAXN][MAXN];
int H, W;

int id(int r, int c) { return r * (W + 1) + c; } // ① 二维坐标转一维

int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]);
    return parent[x];
}

void unite(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx == ry) return;
    if (rnk2[rx] < rnk2[ry]) parent[rx] = ry;
    else if (rnk2[rx] > rnk2[ry]) parent[ry] = rx;
    else { parent[ry] = rx; rnk2[rx]++; }
}

int main() {
    scanf("%d%d", &H, &W);
    for (int i = 0; i <= H; i++)
        for (int j = 0; j <= W; j++) {
            parent[id(i,j)] = id(i,j);
            rnk2[id(i,j)] = 0;
            red[i][j] = false;
        }

    int Q;
    scanf("%d", &Q);
    int dr[] = {-1, 1, 0, 0}, dc[] = {0, 0, -1, 1};
    while (Q--) {
        int t;
        scanf("%d", &t);
        if (t == 1) {
            int r, c;
            scanf("%d%d", &r, &c);
            red[r][c] = true;                    // ② 标记红色
            for (int d = 0; d < 4; d++) {        // ③ 检查四邻居
                int nr = r + dr[d], nc = c + dc[d];
                if (nr >= 1 && nr <= H && nc >= 1 && nc <= W && red[nr][nc])
                    unite(id(r,c), id(nr,nc));   // ④ 红色邻居合并
            }
        } else {
            int ra, ca, rb, cb;
            scanf("%d%d%d%d", &ra, &ca, &rb, &cb);
            bool ok = red[ra][ca] && red[rb][cb] // ⑤ 两格都是红色
                   && find(id(ra,ca)) == find(id(rb,cb)); // ⑥ 同一连通块
            printf("%s\n", ok ? "Yes" : "No");
        }
    }
    return 0;
}

逐行解析：

① 把二维坐标 $(r,c)$ 映射为一维编号，这样就能用一维数组存并查集。
② 涂红一个格子。
③④ 检查四个方向的邻居，如果是红色就合并。
⑤⑥ 查询时先确认两个格子都是红色，再检查连通性。

例题 4：M&A 045 — Easy Graph Problem（★2）

题目： $N$ 个节点 $M$ 条边的连通无向图。有多少个节点满足：比自己编号小的邻居恰好有 1 个？

数据范围： $2 \le N \le 10^5$

—— AtCoder Math & Algorithm 045

分析：这道题虽然出自图论，但可以用并查集的思路来想——不过实际上只需要遍历每个节点的邻居，数比它小的有几个即可。这里作为一道与图连通性相关的练习题。

代码：

#include <cstdio>
#include <vector>
using namespace std;

int main() {
    int N, M;
    scanf("%d%d", &N, &M);
    vector<vector<int>> adj(N + 1);
    for (int i = 0; i < M; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    int ans = 0;
    for (int v = 1; v <= N; v++) {
        int cnt = 0;
        for (int u : adj[v])
            if (u < v) cnt++;      // ① 数比自己编号小的邻居
        if (cnt == 1) ans++;       // ② 恰好1个
    }
    printf("%d\n", ans);
    return 0;
}

逐行解析：

① 对每个节点 $v$ ，遍历它的所有邻居，数有多少个编号比 $v$ 小。
② 如果恰好有 1 个这样的邻居， $v$ 满足条件。
这道题其实不需要并查集，只需邻接表遍历。但它是 M&A 中与图连通性相关的入门题，帮助理解”邻居”概念。

参考文献

教材讲解 — 競技プログラミングの鉄則

第 9 章 9.6 Union-Find + 逆向処理（B66 Typhoon 解说，含完整 UnionFind 类实现）

系统练习 — 競技プログラミングの鉄則

A66 Connect Query（DSU 基础操作）【例题】

实战练习 — 競プロ典型 90 問

模板练习 — ACL Practice Contest

A Disjoint Set Union（DSU 模板题）【例题】

系列索引

第零章基础工具

第一章搜索技术

第二章数学基础

第三章数据结构

第四章图论

第五章动态规划

第六章贪心

第七章字符串

第八章进阶

并查集

你们是不是一伙的？——O(α(n)) 的连通性管理

前言

问题的本质

连通性：图的隐含问题

为什么路径压缩如此重要？

理论 + 代码

基本实现

按秩合并

模拟走一遍

例题

例题 1：TB A66 — Connect Query

例题 2：ACL Practice A — Disjoint Set Union

例题 3：T90 012 — Red Painting（★4）

例题 4：M&A 045 — Easy Graph Problem（★2）

参考文献

系列索引

并查集