并查集汇总

date
Feb 6, 2023
slug
disjoint-set
status
Published
tags
算法
summary
朴素并查集、带权并查集、种类并查集
type
Post
用途朴素并查集带权并查集带权的合并操作find函数种类并查集复杂度练习题银河英雄传说食物链关押罪犯总结Ref

用途

并查集一般用于管理元素所属集合，是一种数据结构，一般有两个操作：
  1. 合并两个集合
  1. 判断两个元素是否属于同一集合

朴素并查集

一般这种并查集是我们最常用的结构，为了区分，我把它成为朴素并查集。
原版
原版的并查集就是实现了开头介绍的合并、判断两个操作。
int p[N];

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

// 找到一个节点的祖先节点
int find(int a)
{
    if (p[a] != a)
        p[a] = find(p[a]);
    return p[a];
}

// 合并两个节点所在的集合
void merge(int a, int b)
{
    int x = find(a), y = find(b);
    p[x] = y;
}
维护size的并查集
可以使用一个size数组来记录集合存在的元素，合并的时候让元素少的集合往元素多的集合合并。
这种合并方式也被称为启发式合并。
相比于原版的合并，效率会高一些。
// p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量
int p[N], size[N], n;

// 返回x的祖宗节点
int find(int x)
{
    if (p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}

// 初始化，假定节点编号是1~n
void init()
{
    for (int i = 1; i <= n; i++)
    {
        p[i] = i;
        size[i] = 1;
    }
}

// 启发式合并
void merge(int a, int b)
{
    int x = find(a), y = find(b);
    if (x == y)
        return;
    if (size[y] < size[x])
        swap(x, y);
    p[x] = y;
    size[y] += size[x];
}
 

带权并查集

维护到祖先节点距离的并查集
const int N = 1e5;

int p[N], d[N];
// p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离

// 返回x的祖宗节点
int find(int x)
{
    if (p[x] != x)
    {
        int u = find(p[x]);
        d[x] += d[p[x]];
        p[x] = u;
    }
    return p[x];
}

// 版本2
int find(int x)
{
		if (p[x] != x)
		{
				int u = p[x];
				p[x] = find(p[x]);
				d[x] += d[u];
		}
		return p[x];
}

// 初始化，假定节点编号是1~n
void init()
{
    for (int i = 1; i <= n; i++)
    {
        p[i] = i;
        d[i] = 0;
    }
}

// 合并a和b所在的两个集合：
void merge(int a, int b)
{
		int px = find(a), py = find(b);
    p[px] = py;
    d[px] = distance; // 根据具体问题，初始化find(a)的偏移量
}

带权的合并操作

我们看一个具体的例子，假设有x和y两个节点，他们的距离是w，而px和py分别是两个节点的祖先节点，它们到祖先的距离分别是d[x]和d[y]。
notion image
现在想要合并px到py，问题是我们怎么设置px和py的距离？
经过观察后发现，合并后x→px→py和x→y→py的距离应该相同，如果不相同就矛盾，因此可以得到d[px] = w + d[y] - d[x]，这是一般情况下权值的计算方式。
在实际题目中，可以根据题目的描述来修改合并方式。

find函数

需要注意的是这里的find函数，一开始d[x]实际上表示的是当前节点离p[x]的距离，而当进行路径压缩后，p[x] 就是这个集合的祖先节点，那么d[x] 的含义就变为了当前节点到祖先节点的距离。所以我们必须先进行路径压缩，才能更新d[x]
// 返回x的祖宗节点
int find(int x)
{
    if (p[x] != x)
    {
				// 寻找祖先节点
        int u = find(p[x]);
        d[x] += d[p[x]]; // 更新到祖先节点的距离
        p[x] = u; // 修改为祖先节点
    }
    return p[x];
}
notion image
如果先更新d[x]，再进行压缩，那么就会得到错误的数据：
int find(int x)
{
    if (p[x] != x)
    {
        d[x] += d[p[x]]; // 没有经过路径压缩的 d[p[x]]，只是父节点到其父节点的距离
        p[x] = find(p[x]); 
    }
    return p[x];
}
这样写就不能正确更新了。
notion image

种类并查集

上面我们介绍的并查集，维护的信息都是具有连通性、传递性的，比如说朋友的朋友是朋友。但有时候题目要求我们维护敌人的敌人是朋友这种关系，种类并查集就是为了解决这个问题而诞生的。
假设需要总元素个数是n，题目需要将维护朋友和敌人两种关系，那么我们就开2n的空间，这里假设n=4。
notion image
我们用1~4维护朋友关系（比如说关在同一个监狱的狱友），用5~8维护敌人关系（比如说关在不同监狱的仇人）。现在假如我们得到信息：1和2是敌人，应该怎么办？
我们merge(1, 2+n), merge(1+n, 2);。这里的意思就是：1是2的敌人，2是1的敌人
notion image
假设2和4又是敌人，我们同样merge(2, 4+n), merge(2+n, 4)
notion image
由于敌人的敌人是朋友，我们可以得出1和4是朋友。当我们查询1和4是否属于同一集合的时候，得到的结果是true。
通过上面的例子我们可以总结一般性规律：
  • 题目有n个元素，有m种类别，则我们需要开n * m的空间
  • 1*n, 2*n, 3*n, …, m*n 分别代表不同的类别
  • 通过链接不同类别的节点，可以描述某种关系。
 

复杂度

复杂度的详细讨论请看：并查集 - OI Wiki (oi-wiki.org)
默认情况下，我们可以认为并查集的每个操作时间复杂度都是很小的常数，近似
空间复杂度是

练习题

下面我们看一些经典的并查集题目，来了解并查集的应用：

银河英雄传说

238. 银河英雄传说 - AcWing题库
题目大意：
N个飞船分布在N列，给定两种操作：
M i j 将第i列的飞船保持原有顺序，接在第j列的尾部
C i j 询问第i号战舰与第j号战舰是否处于同一列，如果同一列，输出它们所隔的战舰。
可以看到题目有很强的集合特征，用并查集来做最合适了
对于M操作，我们执行合并，对于C操作，我们查询i和j是否是同一个集合，如果不是输出-1，否则输出abs(d[i] - d[j]) - 1，其中d[i]表示i节点到祖先节点的距离
初始化时，将d[i]初始化为1，在我们执行合并的时候，假设要执行M 3 2，当前状态如图：
notion image
那么3→2这条边，值应该是多少呢？
考虑合并后，3和6的祖先节点均变为4，而M操作要求我们把节点接在目标集合的尾部，那么3→2的权值应该更新为4，同样地，6→3的权值应该加上4。
我们把结论变得更具有概括性：执行M i j操作时，属于i集合的节点的权值，应该加上j集合的元素个数s[j]。
notion image
现在问题是怎么给i集合的所有权值加上s[j] 呢？我们需要找出所有属于i集合节点的元素然后添加s[j]吗？实际上并查集的路径压缩能很方便的实现这个操作。
还是上面的例子，一开始d[3] = 0 当我们执行M 3 2 的时候，会设置d[3] = s[4] 。只需要执行这步操作后，再将来find的时候，由于路径压缩的原因：
int find(int x)
{
		if (x != p[x])
		{
				int u = find(p[x]);
				d[x] += d[p[x]]; // 路径压缩，更新d[x]
				p[x] = u;
		}
		return p[x];
}
当我们find(6) 的时候，其中d[x] += d[p[x]] 这步操作，会把先前更新的d[3]累加到d[6] 上。从而保证了从6出发，到祖先节点的d都能被正确更新。
总而言之我们只需要修改i集合祖先节点的d，后续就能通过find操作来更新集合中所有节点的d。
下面我们就可以根据分析内容和带权并查集的模板写出代码了：
答案
#include <iostream>
using namespace std;
const int N = 1e4 * 3 + 10;
int p[N], d[N], s[N]; // s表示size，仅有祖先节点才有效
int t, a, b;
char m[2];

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

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

int merge(int x, int y)
{
    int px = find(x), py = find(y);
    p[px] = py;
    d[px] = s[py]; // 应该设置为y所属集合的节点数
    s[py] += s[px];
}

int query(int x, int y)
{
    int px = find(x), py = find(y);
    if (px != py)
        return -1;
    return max(0, abs(d[x] - d[y]) - 1); // 有可能x = y
}
int main()
{
    init();
    scanf("%d", &t);
    for (int i = 0; i < t; i++)
    {
        scanf("%s%d%d", m, &a, &b);
        if (m[0] == 'M')
        {
            if (find(a) == find(b))
                continue;
            merge(a, b);
        }
        else
        {
            printf("%d\n", query(a, b));
        }
    }
}
 

食物链

240. 食物链 - AcWing题库
带权并查集
这道题可以用带权并查集做，我们假设此时的权值d[i]的含义是当前节点i和祖先节点的关系。
根据题目的定义，无非是三种关系：同类、吃、被吃，我们用0，1，2分别来表示这三种关系：
  • d[i] = 0 → 和根节点同类
  • d[i] = 1 → 吃根节点
  • d[i] = 2 → 被根节点吃
举一个例子，下面图中，x是祖先节点，d[y] = 1 表示y吃根节点，d[z] = 2 表示z被根节点吃，d[k] = 3, d[k] % 3 = 0 表示k和x是同类。我们可以根据d的值推断出任意两个节点的关系，比如说z和y就是z吃y的关系，而k和y是同类。
notion image
根据上面的定义，我们现在考虑任意两个节点x和y, x ≠ y
  • 如果x和y在同一集合
    • 如果x和y是同类，那么(d[x] - d[y]) % 3 = 0 成立。
      • 这里表示x和y都和根节点是同类，因此x和y是同类
    • 如果x吃y，那么(d[x] - d[y] - 1) % 3 = 0 成立
      • 这里表示x吃根节点，而y和根节点是同类，因此x吃y
    • 如果x被y吃，那么(d[x] - d[y] - 2) % 3 = 0 成立
      • 这里需要取模，是因为d[x]的值很有可能超过3，所以我们用%3来约束d[i]的值域，便于判断。
  • 如果x和y不在同一个集合，则需要合并，方便以后判断
      • notion image
      比如说上面的情况，给定x和y，以及它们的祖先节点px和py，还有距离d[x]和d[y]，想要合并px到py，那么d[px]应该等于多少呢？
    • 如果x和y是同类，那么(d[x] + d[px] - d[y]) % 3 = 0 成立，可以推断出d[px] = (d[y] - d[x]) %3
    • 如果x吃y，那么(d[x] + d[px] - d[y] - 1) % 3 = 0 成立，可以推断出d[px] = (d[y] - d[x] + 1) %3
经过上面讨论，我们已经可以判断任意两个节点之间的关系了，接下来就可以写出答案了。
题目给出的两类语句：
1 x y表示x和y是同类
2 x y表示x吃y
在我们拿到一个语句的时候，我们先判断这个语句是否是假话，如果是假话，我们什么都不做，否则的话当前话是真话，我们根据真话来执行相应操作，比如说如果x和y属于不同集合，且当前话是真话，那么就要合并x和y的两个集合，方便后续判断
答案
#include <iostream>
using namespace std;
const int N = 50010, M = 1e5 + 10;
int p[N], d[N];
int res;
int n, k;
void init()
{
    for (int i = 0; i < N; i++)
        p[i] = i;
}
int find(int x)
{
    if (x != p[x])
    {
        int u = p[x];
        p[x] = find(p[x]);
        d[x] += d[u];
    }
    return p[x];
}

int main()
{
    init();
    scanf("%d%d", &n, &k);
    int c, x, y;
    while (k--)
    {
        scanf("%d%d%d", &c, &x, &y);
        if (x > n || y > n)
            res++;
        else
        {
            int px = find(x), py = find(y);
            if (c == 1)
            {
                // 如果x和y处于同一集合，且x和y的关系不是同类，那么当前是假话
                if (px == py && (d[x] - d[y]) % 3 != 0)
                    res++;
                else if (px != py) // 如果不是假话，那么我们根据需要来合并
                {
                    // 如果x和y不属于同一个集合，那么合并两个集合
                    p[px] = py;
                    d[px] = (d[y] - d[x]) % 3;
                }
            }
            else
            {
                if (px == py && (d[x] - d[y] - 1) % 3 != 0)
                    res++;
                else if (px != py)
                {
                    // 如果x和y不属于同一个集合，那么合并两个集合
                    p[px] = py;
                    d[px] = (d[y] - d[x] + 1) % 3;
                }
            }
        }
    }
    printf("%d\n", res);
}
 
种类并查集
当前有三类元素，我们开3n的空间。用i + n来表示i的捕食对象，i+2n来表示i的天敌。
这三类集合如果存在联系，那么就是某种关系存在，举个例子
如果(x, y + 2n) 存在一条边，那么就表示 y 是 x 的天敌
如果(x, y + n) 存在一条边，那么就表示 x 吃 y
答案
#include <iostream>
using namespace std;
const int N = 15 * 1e4 + 10;
int n, k, res;
int p[N];
void init()
{
    for (int i = 1; i <= n * 3; i++)
    {
        p[i] = i;
    }
}
int find(int x)
{
    if (x != p[x])
    {
        p[x] = find(p[x]);
    }
    return p[x];
}

bool query(int x, int y)
{
    return find(x) == find(y);
}

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

int main()
{
    scanf("%d%d", &n, &k);
    init();
    int c, x, y;
    while (k--)
    {
        scanf("%d%d%d", &c, &x, &y);
        if (x > n || y > n)
            res++;
        else
        {
            if (c == 1)
            {
                // 如果x吃y或者x被y吃，假话
                if (query(x, y + n) || query(x, y + 2 * n))
                    res++;
                else
                {
                    // 否则x和y同类，则x的猎物是y的猎物，x的天敌是y的天敌
                    merge(x, y);
                    merge(x + n, y + n);
                    merge(x + 2 * n, y + 2 * n);
                }
            }
            else if (c == 2)
            {
                // 如果x和y是同类，或者y是x的天敌，假话
                if (query(x, y) || query(x, y + 2 * n))
                    res++;
                else
                {
                    // 否则x吃y是真的
                    merge(x, y + n);         // x吃y
                    merge(x + n, y + 2 * n); // x的猎物吃y的猎物（传递性）
                    merge(x + 2 * n, y);     // y吃x的天敌
                }
            }
        }
    }
    printf("%d\n", res);
}
这里关键的地方就是merge的选择了，如果是同类的话很好理解，如果x吃y的话，我们要顺着这个逻辑把所有边都merge，不然就没法通过了。
 
 

关押罪犯

257. 关押罪犯 - AcWing题库
种类并查集
我们可以按照边权降序排序，优先将大的边分布在集合之间，就是优先把大冲突的两个节点关在不同监狱，直到无法这么做（无法安排在不同监狱），此时的冲突就是最小的冲突。
显然我们可以分为两类元素，那么需要2 * n的空间。n ~ 2*n 表示敌人。
答案
 
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 4 * 1e4 + 10, M = 1e5 + 10;
int p[N];
struct Edge
{
    int x, y, w;
    bool operator<(const Edge &W) const
    {
        return w > W.w;
    }

} edges[M];

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

bool query(int x, int y)
{
    return find(x) == find(y);
}

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

int main()
{
    for (int i = 0; i < N; i++)
        p[i] = i;
    int n, m;
    int x, y, w;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++)
    {
        scanf("%d%d%d", &x, &y, &w);
        edges[i] = {x, y, w};
    }
    sort(edges, edges + m);
    for (int i = 0; i < m; i++)
    {
        x = edges[i].x, y = edges[i].y, w = edges[i].w;
        if (query(x, y)) // 试图把处于同一集合的元素分开，矛盾
        {
            // 此时的冲突就是无法避免的，输出
            printf("%d\n", w);
            return 0;
        }
        // 标记敌人关系
        merge(x, y + n);
        merge(x + n, y);
    }
    printf("0\n");
    return 0;
}
带权并查集
这道题目也可以用带权并查集+二分来做。
假设答案是mid，那么所有大于mid的边中，边的两端x和y是不连通的，就是说它们属于不同的类别。那么我们可以使用二分来枚举mid，使用一个check()函数来判断当前枚举值是否可行。
check 函数的细节就是，对于所有大于mid的边，如果我们发现两个端点是同一类中，那么就返回false，重复直到没有边，返回true。
如何描述两个点是否属于同一类，可以用带权并查集来实现，0 和 1 分别表示两个类别。
接下来我们可以写出代码：
答案
这里的一个小技巧是用xor来模拟无进位加法，值域限制在0和1，代替%2的操作
#include <cstring>
#include <iostream>
using namespace std;
const int N = 2 * 1e4 + 10, M = 1e5 + 10;
int n, m, x, y, w;
int p[N], d[N];
struct Edge
{
    int x, y, w;
} edges[M];

void init()
{
    memset(d, 0, sizeof d);
    for (int i = 1; i <= n; i++)
        p[i] = i;
}

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

bool check(int mid)
{
    init();
    for (int i = 0; i < m; i++)
    {
        x = edges[i].x, y = edges[i].y, w = edges[i].w;
        if (w <= mid)
            continue;
        int px = find(x), py = find(y);
        if (px == py)
            if (!(d[x] ^ d[y])) // xor 结果为0，表示它们属于同一类
                return false;
        if (px != py)
        {
            p[px] = py;
            d[px] = d[x] ^ d[y] ^ 1; // 因为是不同类，所以要 ^ 1
        }
    }
    return true;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++)
    {
        scanf("%d%d%d", &x, &y, &w);
        edges[i] = {x, y, w};
    }
    int l = 0, r = 1e9;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    printf("%d", r);
}
当然这里也可以把带权并查集换成种类并查集，同样用二分解决，不过直接用种类并查集的性质比较优雅。
答案
#include <cstring>
#include <iostream>
using namespace std;
const int N = 2 * 1e4 + 10, M = 1e5 + 10;
int n, m, x, y, w;
int p[N * 2];
struct Edge
{
    int x, y, w;
} edges[M];

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

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

bool query(int x, int y) { return find(x) == find(y); }

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

bool check(int mid)
{
    init(n);
    for (int i = 0; i < m; i++)
    {
        x = edges[i].x, y = edges[i].y, w = edges[i].w;
        if (w <= mid)
            continue;
        if (query(x, y))
            return false;
        merge(x, y + n);
        merge(x + n, y);
    }
    return true;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++)
    {
        scanf("%d%d%d", &x, &y, &w);
        edges[i] = {x, y, w};
    }
    int l = 0, r = 1e9;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    printf("%d", r);
}

总结

本文介绍了朴素并查集，带权并查集，种类并查集，这里总结一下他们的区别
  • 朴素并查集：最常用的一类并查集，用来管理元素的从属关系。
  • 带权并查集：在朴素并查集上添加了权重d ，d 可以根据题目的不同来表示不同的含义，使用时需要确定merge和find操作如何更新d
  • 种类并查集：一般维护若干个n的区间，每个区间表示不同含义，通过merge不同区间的节点，标识某种关系的存在
一般种类并查集都可以用带权并查集来做，我们定义好d的含义即可，而且只有总节点数的比较小情况下才能用种类并查集，不然开若干个区间可能会溢出。但是种类并查集的思想和含义也比较简洁，有的时候可以利用它的性质来巧妙解题。

Ref

并查集 - OI Wiki (oi-wiki.org)
并查集到带权并查集 - zhxmdefj - 博客园 (cnblogs.com)
算法学习笔记(7)：种类并查集 - 知乎 (zhihu.com)
 
更多例题：
hdu1232 城镇交通
poj1611 感染的学生
hdu3038
POJ2492

© hhmy 2019 - 2023

powered by nobelium