并查集

概念

并查集（Disjoint Set Union，简称 DSU，又称 Union-Find）是一种用于维护若干不相交集合的树形数据结构，实现为森林。森林中的每一棵树代表一个集合，树中的结点代表集合中的元素，树的根结点是集合的代表元（根节点），用来唯一标识这个集合。

并查集支持两种核心操作：

1. 合并（union）：把两个元素所在的集合合并成一个集合；
2. 查询（find）：查找某一元素所在集合的代表元，常用于判断两个元素是否属于同一个集合（两个元素的代表元相同则在同一集合中）。

初始化

我们使用数组 $p$ 实现并查集，约定如下：

1. $N$ 个元素的编号分别为 $1\sim N$；
2. $p[i]$ 存储元素 $i$ 的父结点，例如元素 $x$ 的父结点为 $p[x]$；
3. 根结点的父结点是它自身，即 $p[i]=i$ 当且仅当 $i$ 是它所在集合的代表元。

初始时，每个元素各自单独构成一个集合，因此每个元素都是自己所在集合的代表元。

const int N = 100010;
int p[N];

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

查询（find）

查询元素 $x$ 所属集合时，从 $x$ 出发不断询问它的父结点是谁，如果父结点不是代表元（根结点），就继续询问父结点的父结点，直到找到满足 $p[i]=i$ 的根结点，该根结点即为 $x$ 所在集合的代表元。

// 迭代实现
int find(int x) {
    while (p[x] != x) {
        x = p[x];
    }
    return x;
}

// 递归实现
int find(int x) {
    if (p[x] != x) return find(p[x]);
    return x;
}

不加任何优化时，若合并操作使树退化成一条链，一次查询最坏需要从当前结点一路走到根，时间复杂度为 $O(N)$；$m$ 次操作最坏为 $O(Nm)$。

路径压缩

在查询某个元素所属集合的过程中，我们会沿路径询问它的所有祖先，而这条路径上的所有结点显然都属于同一个集合。 因此可以在回溯时把路径上的每个结点直接连接到根结点上，这就是路径压缩。路径压缩只改变树的形态，不改变集合的划分。

// 带路径压缩的 find：找到根后，把路径上的所有结点直接挂到根上
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

单独使用路径压缩时，$m$ 次操作的均摊时间复杂度为 $O(m\log N)$；与下文的启发式合并结合后，可进一步降为 $O(m\alpha (N))$。

合并（merge）

合并两个集合，即合并两棵树，只需将一棵树的根结点接到另一棵树的根结点上。合并后，$x$ 所在集合与 $y$ 所在集合的所有元素都属于同一个集合。

void merge(int x, int y) {
    // 把 x 所在集合合并到 y 所在集合上
    p[find(x)] = find(y);
}

若不配合优化，合并后树可能退化成链，单次查询、合并的复杂度最坏为 $O(N)$。

AcWing 836. 合并集合

题意：一共有 $n$ 个数，编号为 $1\sim n$，初始时每个数各自在一个集合中。共 $m$ 个操作，M a b 表示把编号为 $a$、$b$ 的两个数所在集合合并（若已在同一集合则忽略），Q a b 询问 $a$、$b$ 是否在同一集合中。$1\le n,m\le {10}^5$。

思路：这是并查集模板题。合并直接调用 merge(a, b)，询问判断 find(a) == find(b)，是则输出 Yes，否则输出 No。

输入样例：

4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4

输出样例：

Yes
No
Yes

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

const int N = 1e5 + 10;
int p[N];

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

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

void merge(int x, int y) {
    p[find(x)] = find(y);
}

int main() {
    int n, m;
    cin >> n >> m;

    init(n);

    while (m--) {
        char op[2];
        int a, b;
        scanf("%s%d%d", op, &a, &b);

        if (op[0] == 'M') {
            merge(a, b);
        } else {
            if (find(a) == find(b)) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
    }

    return 0;
}

启发式合并

合并两个集合时，选择哪棵树作为合并后新树的根结点，会影响后续操作的效率。一个自然的想法是：把结点数较少（或深度较小）的树接到结点数较多（或深度较大）的树上，防止树退化成链。这类优化统称为启发式合并。

按秩合并

按秩合并用数组 $rk$（秩，即树的深度）记录每个根结点对应树的深度（非根结点的 $rk$ 没有意义）。合并时把深度较小的树接到深度较大的树上；初始化时每个结点的 $rk$ 为 $1$，当两棵深度相同的树合并时，新根的深度加 $1$。

注意数组名不使用 rank：在 using namespace std; 的环境下会与标准库 std::rank 冲突，导致编译失败。

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

void merge(int x, int y) {
    int px = find(x), py = find(y);
    if (px == py) return;

    // 深度小的树接到深度大的树上
    if (rk[px] > rk[py]) swap(px, py);
    p[px] = py;

    // 两棵树深度相同，新根 py 的深度加 1
    if (rk[px] == rk[py]) rk[py]++;
}

性质：一棵树的深度只有在两棵深度相同的树合并时才会增加 1，因此任意时刻树的深度不超过 $O(\log N)$，单次查询、合并的时间复杂度为 $O(\log N)$。

按大小合并

另一种启发式合并是维护集合大小 $sz[i]$（$i$ 为根时表示所在集合的结点数），每次把较小的集合接到较大的集合上。它同样保证树高为 $O(\log N)$，并且可以顺带维护每个连通块的大小，常用于"连通块中点的数量"这类问题。

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

void merge(int x, int y) {
    int px = find(x), py = find(y);
    if (px == py) return;

    // 把较小的集合接到较大的集合上
    if (sz[px] < sz[py]) swap(px, py);
    p[py] = px;
    sz[px] += sz[py];
}

复杂度

同时使用路径压缩 + 按秩合并（或按大小合并）时，$m$ 次操作的总均摊时间复杂度为 $O(m\alpha (N))$，其中 $\alpha$ 是反阿克曼函数。$\alpha (N)$ 增长极其缓慢，常见题目规模下可视为常数（$N\le {10}^{18}$ 时 $\alpha (N)\le 4$），这就是并查集单次操作"近似 $O(1)$"说法的来源。

带权并查集

在基础并查集的基础上，额外维护"每个结点与父结点之间的关系"，这样的并查集称为带权并查集。

常见的实现是维护距离数组 $d$：$d[x]$ 表示 $x$ 到父结点 $p[x]$ 的距离（可以是真实距离，也可以是某种关系编码）。在 find 路径压缩时，$x$ 被直接连到根结点，此时把 $x$ 到原父结点的距离与父结点到根的距离累加，即可把 $d[x]$ 维护为 $x$ 到根结点的距离：

int find(int x) {
    if (p[x] != x) {
        int root = find(p[x]);
        d[x] += d[p[x]];   // 累加前 p[x] 还是原来的父结点
        p[x] = root;
    }
    return p[x];
}

合并两棵根分别为 $px$、$py$ 的树时，把 $px$ 接到 $py$ 上，需要根据题目给出的 $x$、$y$ 之间的关系确定 $d[px]$。设 $x$、$y$ 到根的距离分别为 $d[x]$、$d[y]$，关系通常写成模 $k$ 的同余式，解出 $d[px]$ 即可，具体推导见下方例题。

洛谷 P2024. [NOI2001] 食物链

题意：三类动物 $A,B,C$ 构成环形食物链 $A$ 吃 $B$，$B$ 吃 $C$，$C$ 吃 $A$。现有 $N$ 个动物（编号 $1\sim N$），依次给出 $K$ 句话，1 x y 表示 $x$ 与 $y$ 同类，2 x y 表示 $x$ 吃 $y$。一句话是假话当且仅当它与之前的真话矛盾、$x$ 或 $y$ 超出 $[1,N]$、或 $x$ 吃 $x$。求假话总数。$1\le N\le 5\times {10}^4$，$1\le K\le {10}^5$。

思路：用带权并查集维护 $d[x]mod3$：$0$ 表示 $x$ 与根同类，$1$ 表示 $x$ 吃根，$2$ 表示根吃 $x$。于是 $x$、$y$ 同类当且仅当 $(d[x]-d[y])mod3=0$，$x$ 吃 $y$ 当且仅当 $(d[x]-d[y])mod3=1$。合并时把 $px$ 接到 $py$ 上：同类令 $d[px]=d[y]-d[x]$，$x$ 吃 $y$ 令 $d[px]=d[y]+1-d[x]$，即可使新树中的关系满足上述同余式。注意 C++ 中负数取模仍为负数，本题只需判断模 $3$ 是否为 $0$，可直接使用 %。

输入样例：

100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5

输出样例：

3

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

const int N = 5e4 + 10;
int p[N], d[N]; // d[x] 表示 x 到父结点的距离，路径压缩后为到根结点的距离
int n, k, ans;

int find(int x) {
    if (p[x] != x) {
        int root = find(p[x]);
        d[x] += d[p[x]]; // 累加得到 x 到根的距离
        p[x] = root;
    }
    return p[x];
}

int main() {
    scanf("%d%d", &n, &k);

    for (int i = 1; i <= n; i++) p[i] = i;

    while (k--) {
        int o, x, y;
        scanf("%d%d%d", &o, &x, &y);

        // d[x] % 3 == 0：x 与根同类
        // d[x] % 3 == 1：x 吃根
        // d[x] % 3 == 2：x 被根吃
        if (x > n || y > n) {
            ans++;
            continue;
        }

        int px = find(x), py = find(y);
        if (o == 1) { // x 与 y 是同类
            if (px == py && (d[x] - d[y]) % 3 != 0) ans++;
            else if (px != py) {
                p[px] = py;
                d[px] = d[y] - d[x];
            }
        } else { // x 吃 y
            if (px == py && (d[x] - d[y] - 1) % 3 != 0) ans++;
            else if (px != py) {
                p[px] = py;
                d[px] = d[y] + 1 - d[x];
            }
        }
    }

    printf("%d\n", ans);

    return 0;
}

扩展域并查集

有的题目中元素之间存在多种关系（如"朋友 / 敌人"），此时可以把每个元素拆成多个点（域），用不同的点表示该元素的不同状态，再统一放入同一个并查集中。已知的关系转化为"某些状态点应处于同一集合"，用合并表达，这种方法称为扩展域（拆点）并查集。

洛谷 P1892. [BOI2003] 团伙

题意：$n$ 个人之间存在朋友和敌人两种关系：朋友的朋友是朋友，敌人的敌人是朋友；两个人在同一团伙内当且仅当他们是朋友。给出 $m$ 条关系（F x y 表示朋友，E x y 表示敌人），求最多可能的团伙数。$2\le n\le 1000$，$1\le m\le 5000$。

思路：把每个人 $i$ 拆成两个点：$i$ 表示"朋友域"，$i+n$ 表示"敌人域"。F x y 合并 $x$、$y$ 的朋友域；E x y 表示 $x$ 与 $y$ 的敌人是朋友、$y$ 与 $x$ 的敌人是朋友，因此合并 $x$ 与 $y+n$、合并 $y$ 与 $x+n$。这样"敌人的敌人是朋友"自然成立。最后统计 $1\sim n$ 中互不相同的根结点个数，即为团伙数。

输入样例：

6
4
E 1 4
F 3 5
F 4 6
E 1 2

输出样例：

3

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

const int N = 1010;
int p[N * 2], root[N];
int n, m, ans;

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

int main() {
    scanf("%d%d", &n, &m);

	// 初始化并查集，每个点拆成两个点，一个表示朋友域，一个表示敌人域
    for (int i = 1; i <= 2 * n; i++) p[i] = i;

    while (m--) {
        char o;
        int x, y;
        scanf(" %c%d%d", &o, &x, &y);

        if (o == 'F') {
            p[find(x)] = find(y);      // 朋友合并
        } else {
            p[find(x)] = find(y + n);  // x 与 y 的敌人是朋友
            p[find(y)] = find(x + n);  // y 与 x 的敌人是朋友
        }
    }

    // 统计 1 ~ n 中不同根结点的个数，即团伙数
    for (int i = 1; i <= n; i++) root[i] = find(i);
    sort(root + 1, root + n + 1);
    for (int i = 1; i <= n; i++) {
        if (root[i] != root[i - 1]) ans++;
    }

    printf("%d\n", ans);

    return 0;
}

洛谷 P2024. [NOI2001] 食物链的扩展域并查集解法：

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

const int N = 1e5 + 10;
int p[3 * N];
int n, m, ans;

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

/*
    [1, N] 同类域
    [N + 1, 2 * N] 捕食域
    [2 * N + 1, 3 * N] 天敌域
*/
int main() {
	cin >> n >> m;

	for (int i = 1; i <= 3 * n; i++) p[i] = i;

	while (m--) {
		int o, x, y;
		cin >> o >> x >> y;

		if (x > n || y > n) ans++;
		else {
			int px = find(x), py = find(y);
			if (o == 1) {
                if (find(x + n) == find(y) || find(x) == find(y + n)) ans++;
                else {
                    p[find(x)] = find(y);
                    p[find(x + n)] = find(y + n);
                    p[find(x + 2 * n)] = find(y + 2 * n);
                }
			} else {
				if (find(x) == find(y) || find(x) == find(y + n)) ans++;
                else {
                    p[find(x)] = find(y + 2 * n);
                    p[find(x + n)] = find(y);
                    p[find(x + 2 * n)] = find(y + n);
                }
			}
		}
	}

	cout << ans << endl;

    return 0;
}

应用

并查集常与其他算法配合使用：

1. Kruskal 求最小生成树：边按权值从小到大排序，依次加入两端点不在同一集合的边，用并查集判断连通性；
2. Tarjan 离线求最近公共祖先（LCA）：用并查集维护已经回溯完的子树；
3. 维护无向图的连通块数量与大小；
4. 离线处理只有加边操作的动态连通性问题（可结合倒序删边）。

洛谷 P3958. [NOIP2017 提高组] 奶酪

题意：奶酪中有 $n$ 个球形空洞，半径均为 $r$，奶酪下表面为 $z=0$，上表面为 $z=h$。两个空洞球心距不超过 $2r$ 时视为连通（相交或相切）。问是否存在一条从下表面到上表面的通路。$1\le n\le 1000$，$1\le h,r\le {10}^9$。

思路：用并查集把所有相互连通的空洞合并。若某个空洞与下表面相切或相交（$z-r\le 0$），另一个空洞与上表面相切或相交（$z+r\ge h$），且二者属于同一集合，则答案为 Yes，否则为 No。为避免浮点误差，代码直接比较距离的平方（$4r^2$），坐标与 $r$ 都在 ${10}^9$ 以内，用 long long 足够。

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

const int N = 1010;
int p[N];

struct Point {
    long long x, y, z;
} pt[N];

int T, n, h, r;

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

long long dis(const Point& a, const Point& b) {
    long long dx = a.x - b.x;
    long long dy = a.y - b.y;
    long long dz = a.z - b.z;
    return dx * dx + dy * dy + dz * dz;
}

int main() {
    scanf("%d", &T);

    while (T--) {
        scanf("%d%d%d", &n, &h, &r);

        for (int i = 1; i <= n; i++) p[i] = i;

        vector<int> top, bottom;
        for (int i = 1; i <= n; i++) {
            scanf("%lld%lld%lld", &pt[i].x, &pt[i].y, &pt[i].z);

            if (pt[i].z - r <= 0) bottom.push_back(i); // 与下表面相切或相交
            if (pt[i].z + r >= h) top.push_back(i);    // 与上表面相切或相交

            for (int j = 1; j < i; j++) {
                // 球心距 <= 2r，等价于距离平方 <= 4r^2
                if (dis(pt[i], pt[j]) <= 4LL * r * r) {
                    int pi = find(i), pj = find(j);
                    if (pi != pj) p[pi] = pj;
                }
            }
        }

        bool ok = false;
        for (int i = 0; i < (int)top.size() && !ok; i++) {
            for (int j = 0; j < (int)bottom.size(); j++) {
                if (find(top[i]) == find(bottom[j])) {
                    ok = true;
                    break;
                }
            }
        }
        puts(ok ? "Yes" : "No");
    }

    return 0;
}

参考资料

• OI Wiki - 并查集
• 《算法竞赛进阶指南》（李煜东）