并查集

· · 算法·理论

大家好，今天我要为大家讲解并查集。

让我们先来认识一下并查集吧！

并查集是在C++中的一个算法，英文名叫 Disjoint Set Union。

并查集是一种树形数据结构，用于处理一些不相交集合的合并及查询问题。通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，这样就可以查询某个元素所在的集合、与这个元素在一个集合中的元素，以及更多。

只说这些肯定不行，接下来我将详细介绍。

我来举个形象的例子，众所周知，有人的地方就有江湖，假设有一些门派，各个门派都有一些人，而当两个人相遇时，如果相互不认识，会自报家门，也就是说自己的师父是谁，如果不一样，那么就说自己师父的师父是谁，以此类推，如果一直说到掌门人不一样，那么说明这两个人不是一个门派的，就会打一架，如果报到掌门人发现一样，那么说明是一个门派的，就不打架了，坐下来喝酒。（并查集中叫：查询）

而在江湖中也有其他事情，两个门派要合起来，于是两个门派就合并了，以后就变成了一个门派，互相相遇就不能打架了。（并查集中叫：合并）

我举的例子就是并查集的原理，第一种叫做查询，第二种叫做合并，并查集就只有这两种操作，怎么样，是不是十分简单，很好理解呢！

那我用专业的语言再来说一遍并查集吧，毕竟不能只靠形象比喻来理解知识。

并查集支持如下两种操作：

既然概念我们已经理解了，那么接下来重点来看实现。

首先，我们怎么模拟并查集那种结构呢？

举个例子awa：

我们说过要用数组存储数据，那么我们定义一个名叫 father 的数组存储父节点的编号，那么 father 数组目前情况如下：

0 1 2 3 4 5 6 7 8
1 1 1 4 4 6 6 7

比如我们查询 3 和 5 是否在同一个集合内时，我们首先看 3，它集合中的根节点是 1；再看 5，5 集合中的根节点是 4，不相同，说明 3 和 5 不在同一个集合中。

再比如我们要将 5 和 8 所在的两个集合合并成一个集合，那么我们就让 5 所在集合的根节点 4 “认贼作父”，直接将 father 数组中下标为 4 的值改为 8 所在集合的根节点 6，就能成功合并了。

合并之后图就变成了这样：

作者注：其实不一定要把 4 接在 6 下面，把 6 接在 4 下面也可以，甚至把 5 也接在 6 下面也没问题，只要合并之后两个集合所有元素都在一个集合里面就行。

那么我们开始尝试写出实现以上功能的代码吧！（作者自认为码风良好，代码可读性还算高，如有建议请在评论区提出）

注：本代码经过实测是没有任何问题的，且此代码为并查集模板，可以复制使用，如存在与您的代码有差异，为正常现象，毕竟怎么可能所有人的代码都是一样的呢）

假设有 n 个点，n 的范围为 1 \le n \le 10^5。

首先代码开头的变量、数组的定义。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 1e5 + 5;
ll n;
ll father[maxn];

首先我们要让这 n 个点先初步出现在我们的并查集中，就要把每个点初始化，也就是先把每个点在 father 数组中写成自己。

代码实现：

//初始化 
void init() {
    for (ll i = 1; i <= n; i++) {
        father[i] = i;
    }
}

时间复杂度 O(n)。

接下来我们来写查找函数（以下的代码是没有优化的，优化待会再讲）：

//查找函数 
ll find(ll x) {
    if (father[x] == x) return x;
    return find(father[x]);
}

解析：这段代码是用来查找自己集合中的根节点。如果自己的父亲就是自己，那么直接返回自己，也就是自己就是自己集合中的根节点，否则，继续查找，以此类推，最后会求出祖先。

时间复杂度 O(n)。

合并函数：

//合并函数 
void merge(ll x, ll y) {
    father[find(x)] = find(y);
}

解析：首先先求出第一个要合并的点的根节点，再求出第二个，将第一个根节点的父亲变为第二个根节点的父亲。

时间复杂度 O(n)。

还记得我刚才说过在查找函数时有一个优化吗，现在我们来讲讲。

老规矩，拿个例子讲。

这是一个极端情况，这个例子中，如果我们从 4 进行 find()，那么我们需要把所有的点全都走一遍，那么时间复杂度自然就高了。

那么该怎么办呢？

自然是有办法的，我们要使用 路径压缩。

拿刚才的例子继续说，进行路径压缩，就是把 3 不再接在 2 下面，4 也不再接在 3 下面，全部接到 1 下面：

这样就可以大大滴节省查找根节点的时间。

优化后的代码：

//查找函数 
ll find(ll x) {
    if (father[x] == x) return x;
    return father[x] = find(father[x]);
}

也就只加上了 father[x] = 这几个字，没有什么理由不去把如此简洁的优化添加上。

那么相信大家会问，优化后的时间复杂度有提高吗？是多少？

罗伯特·塔扬（Robert Tarjan） 证明过，find 函数优化后时间复杂度变为 O(\alpha \left ( n \right )) ，merge 也变成了 O(\alpha \left ( n \right )) ，其中 \alpha 是一个函数，即使在 n 非常大的时候，\alpha \left ( n \right ) 依然是一个小于 5 的常数。

题外话：这个人就是你们熟悉的 tarjan 算法 的发明者。

部分代码都讲完了，现在给出模板代码！

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 1e5 + 5;
ll n;
ll father[maxn];
//初始化 
void init() {
    for (ll i = 1; i <= n; i++) {
        father[i] = i;
    }
}

//查找函数 
ll find(ll x) {
    if (father[x] == x) return x;
    return father[x] = find(father[x]);
}

//合并函数 
void merge(ll x, ll y) {
    father[find(x)] = find(y);
}

int main() {
    cin >> n;
    init();
    return 0;
}

接下来我们来做几道题目看看是否掌握吧！

并查集初学练习题目（推荐）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 2e5 + 5;
ll n, m, z, x, y;
ll father[maxn];
//初始化 
void init() {
    for (ll i = 1; i <= n; i++) {
        father[i] = i;
    }
}

//查找函数 
ll find(ll x) {
    if (father[x] == x) return x;
    return father[x] = find(father[x]); //路径压缩 
}

//合并函数 
void merge(ll x, ll y) {
    father[find(x)] = find(y);
}

int main() {
    cin >> n >> m;
    init();
    for (ll i = 1; i <= m; i++) {
        cin >> z >> x >> y;
        if (z == 1) {
            merge(x, y);
        } else if (z == 2) {
            if (find(x) == find(y)) cout << "Y" << endl;
            else cout << "N" << endl;
        }
    }
    return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 5005;
ll n, m, p, x, y, pi, pj;
ll father[maxn];
//初始化 
void init() {
    for (ll i = 1; i <= n; i++) {
        father[i] = i;
    }
}

//查找函数 
ll find(ll x) {
    if (father[x] == x) return x;
    return father[x] = find(father[x]); //路径压缩 
}

//合并函数 
void merge(ll x, ll y) {
    father[find(x)] = find(y);
}

int main() {
    cin >> n >> m >> p;
    init();
    for (ll i = 1; i <= m; i++) {
        cin >> x >> y;
        merge(x, y);
    }
    while (p--) {
        cin >> pi >> pj;
        if (find(pi) == find(pj)) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 1005;
ll n, m, u, v;
ll father[maxn];
//初始化 
void init() {
    for (ll i = 1; i <= n; i++) {
        father[i] = i;
    }
}

//查找函数 
ll find(ll x) {
    if (father[x] == x) return x;
    return father[x] = find(father[x]); //路径压缩 
}

//合并函数 
void merge(ll x, ll y) {
    father[find(x)] = find(y);
}

int main() {
    while (1) {
        cin >> n >> m;
        if (n == 0) break;
        init();
        for (ll i = 1; i <= m; i++) {
            cin >> u >> v;
            merge(u, v);
        }
        ll ans = 0;
        for (ll i = 1; i <= n; i++) {
            if (father[i] == i) ans++;
        }
        cout << ans - 1 << endl;
    }
    return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 2e4 + 5;
ll n, m, k;
string s, u, v;
map<string, string> father;
//初始化 
void init() {
    for (ll i = 1; i <= n; i++) {
        cin >> s;
        father[s] = s;
    }
}

//查找函数 
string find(string x) {
    if (father[x] == x) return x;
    return father[x] = find(father[x]); //路径压缩 
}

//合并函数 
void merge(string x, string y) {
    father[find(x)] = find(y);
}

int main() {
    cin >> n >> m;
    init();
    for (ll i = 1; i <= m; i++) {
        cin >> u >> v;
        merge(u, v);
    }
    cin >> k;
    while (k--) {
        cin >> u >> v;
        if (find(u) == find(v)) cout << "Yes." << endl;
        else cout << "No." << endl;
    }
    return 0;
}

学到这里想必你已经熟练掌握了并查集的操作，快去做题试试你的学习成果吧！

留个小作业：

在做这些练习题的过程中，你可以看看题解，看看他们对这些题目的巧思妙想。

如果你在读的过程中发现问题，可以在评论区提出！

求个赞qwq。

（注：因为我不会做图，所以文中的几个图是我找别人帮我做的）