参考：并查集 - OI-wiki

解决的核心问题：现在有 n 个互不相交的有限集 S_1, \dots, S_n。给定一个元素 x，判断元素属于哪个集合。同时，这些集合可能合并为一个新集合：S_1' = S_1 \cup S_2，还要支持这种合并。

使用代数和关系的概念，并查集维护了一个有限 （链接未公开），并支持查询两个元素是否等价，以及合并两个较小的等价类。

并查集原理

使用森林（许多树）来实现这样的功能。每个元素只需记录自己的父节点是谁，而根节点的父节点规定为自己。这样，这个森林就可以用一个数组来存储。

初始化

初始化时，每个节点是一颗独立的树，令其父节点为自身。

假设一共有 n 个元素，则初始化程序为

const size_t MAXN = 1e6 + 5; // 数组大小
size_t n, fa[MAXN];
for (size_t i = 1; i <= n; i++)
{
    fa[i] = i;
}

查询

朴素查询算法

朴素的查询，只需要逐级向上寻找根节点即可。根节点即代表所属集合。

size_t find(size_t x)
{
    while (x != fa[x])
    {
        x = fa[x];
    }
    return x;
}

路径压缩

由于我们只关心元素属于哪一个集合，并不关心元素之间具体的树形结构关系，因此可以在查询时顺便将经过的节点进行路径压缩。

路径压缩的非递归代码如下：

#include <stack>

size_t find(size_t x)
{
    stack<size_t> s;
    while (x != fa[x])
    {
        s.push(x);
        x = fa[x];
    }
    size_t r = x;
    while (!s.empty())
    {
        x = s.top();
        s.pop();
        fa[x] = r;
    }
    return r;
}

可以将以上代码改为更简单的递归写法：

size_t find(size_t x)
{
    if (x != fa[x])
    {
        fa[x] = find(fa[x]);
        // 这里递归结束后，fa[x] 一定已经是根节点，不需要循环
    }
    return fa[x];
}

以上“短小精悍”代码的原理：对于每个非根的节点 x_i，都会展开一层新的递归，寻找 \text{fa}(x_i) 的根，直到找到根节点才会停止产生新的递归，产生递归栈，形参序列为：x_n , x_{n - 1}, \dots, x_1, x_0 ，其中 x_0 是根节点。此时开始返回值，对于离根最近的 x_1，令 \mathrm{fa}(x_1) = x_0 ，返回 \mathrm{fa}(x_1) = x_0 ；然后到 x_2 ，程序会令 \mathrm{fa}(x_2) 等于上一步的返回值 x_0 ，得到 \mathrm{fa}(x_2) = x_0 ，并再次返回 x_0；如此递归，路径上的所有点都会有 \mathrm{fa}(x_i) = x_0 ，并且程序最终的返回值也是根节点 x_0 。

也可以压行写成：

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

合并

朴素合并方法

只需要将一棵树的根节点的父节点设为另一棵树，就实现了合并。

void merge(size_t x, size_t y)
{
    x = find(x);
    y = find(y);
    fa[x] = y;
}

启发式合并

可以同时记录并查集的大小（节点数）或深度，将较小的并查集的根部连接到较大的并查集上。这样需要额外开一个 siz 数组记录并查集大小，初始化时，siz 的所有值都应设置为 1 。

注意，实现上需要特判 x = y，否则 siz 会计算错误。

void merge(size_t x, size_t y)
{
    x = find(x);
    y = find(y);
    if (x == y) // 特判
    {
        return;
    }
    if (siz[x] < siz[y])
    {
        swap(x, y);
    }
    fa[y] = x;
    siz[x] += siz[y];
}

完整代码

仅路径压缩：

const int MAXN = 1e5 + 5;

size_t fa[MAXN], siz[MAXN];

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

size_t find(size_t x)
{
    if (x != fa[x])
    {
        fa[x] = find(fa[x]);
    }
    return fa[x];
}

void merge(size_t x, size_t y)
{
    x = find(x);
    y = find(y);
    fa[x] = y;
}

包含启发式合并：

const int MAXN = 1e5 + 5;

size_t fa[MAXN], siz[MAXN];

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

size_t find(size_t x)
{
    if (x != fa[x])
    {
        fa[x] = find(fa[x]);
    }
    return fa[x];
}

void merge(size_t x, size_t y)
{
    x = find(x);
    y = find(y);
    if (x == y)
    {
        return;
    }
    if (siz[x] >= siz[y])
    {
        fa[y] = x;
        siz[x] += siz[y];
    }
    else
    {
        fa[x] = y;
        siz[y] += siz[x];
    }
}

代码常见错误

merge 函数中的 x = find(x); y = find(y); 错写成了 x = fa[x]; y = fa[y];。数据不强的情况下，这种写法能通过不少测试点，因为已经路径压缩。

并查集复杂度

空间复杂度

显然为 O(n) 。

使用路径压缩和启发式合并

同时使用路径压缩和启发式合并时，若操作数为 m，则时间复杂度为 O(m \alpha(n))，其中 \alpha(n) 为反 Ackermann 函数，增长非常缓慢，由于题目通常数据范围有限，可以认为是一个常数。

若只使用路径压缩，不使用启发式合并，则平均时间复杂度为 O(m\alpha(m, n)) ，最坏时间复杂度为 O(m \log n)。

若只使用启发式合并，不使用路径压缩，则最坏时间复杂度为 O(m \log n) 。

并查集与等价关系

并查集常常用于判断 （链接未公开），因为算法本身“代表元”的使用便和等价关系有关。具体地说，它可以判断两个元素是否等价（属于同一个等价类），以及合并两个等价类（特殊地，包括把一个新的点归入一个等价类中）。

等价关系非常常见，无向图的连通分支便构成一个等价类，一个无向图可以按连通性划分为几个等价类（连通分支）。

应用

• 用于划分等价类以及判断两元素是否等价。
  • NOI2015 - 程序自动分析
• 用于判断图上两点的连通性，以及维护“不断加边”的图的信息。
  • 例如 Kruskal 算法求最小生成树

种类并查集

介绍

参考：算法学习笔记(7)：种类并查集 - 知乎

维护对立集合时使用。例如“敌人的敌人是朋友”。

形式化地说，现在有两个集合和 n 个变量，种类并查集能完成以下工作：

• 询问 x_i 和 x_j 是否一定处在相同的集合之中；
• 询问 x_i 和 x_j 是否一定处在不同的集合之中；
• 添加一个条件：x_i 和 x_j 在同个集合中（须保证不矛盾）；
• 添加一个条件：x_i 和 x_j 不在同一个集合中（须保证不矛盾）。

具体算法为：开大小为 2n 的并查集，i 和 i + n 都表示第 i 个变量 x_i。当添加条件 x_i 和 x_j 不在一个集合中时，连接 i 和 {j + n}、j 和 i + n。

例题

P1525 关押罪犯

给定 n 个罪犯，有 m 对罪犯之间存在怨气值。将他们分配到两个监狱，使同个监狱内的罪犯的最大怨气值最小。