C++高级数据结构之并查集

什么是并查集

并查集（Union Find Set）是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。

并查集定义了如下的三种操作：

1、makeSet(s)：建立一个新的并查集，其中包含s个单元素集合。

2、unionSet(x, y)：把元素x和元素y所在的集合合并，要求x和y所在的集合不相交，如果相交则不合并。

3、find(x)：找到元素x所在的集合的代表，可用于判断两个元素是否处在同一个集合中。

这三种操作的时间复杂度都不超过O(log2n)，其中n是元素的个数。

并查集的实现

并查集通常采用数组来实现，如果要表示多个集合，就把这个数组当成一个森林，树的根节点表示一个集合。

int father[N]; // 父节点数组

// 初始化
for (int i = 0; i < N; i++) {
    father[i] = i;
}

// 查找
int find(int x) {
    if (father[x] != x) father[x] = find(father[x]);
    return father[x];
}

// 合并
void unionSet(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx != fy) father[fx] = fy;
}

上面的代码实现就是采用了路径压缩，每次查找时直接将x的祖先节点赋值为根节点。

并查集的应用

并查集在解决一些组团及连通性问题非常高效。

例一

LeetCode 1319 连通网络的操作次数

题目描述：

一个计算机连接网络，需要进行n次操作。每次操作选择两台已经连接到网络上的电脑x、y，并且使它们之间产生一条新的连接。如果这两台电脑已经有直接的连接或者通过其他电脑建立了连接，那么将不再重复执行连接。计算机通过网络连接后可以形成若干个分组。其中网络连接次数最少的操作顺序，输入为n对互不相同的正整数x、y，表示连接x号计算机和y号计算机。连接计算机时连接次数不超过n-1次。

输入：4

[[0,1],[0,2],[1,2]]

输出：1

解释：

先连接 0 和 1，需要一次操作。

再连接 1 和 2，需要一次操作。

总共需要 2 次操作。

代码如下：

class Solution {
public:
    int father[10005];
    int n;

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

    int makeSet() {
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            father[i] = i;
            cnt++;
        }
        return cnt;
    }

    int unionSet(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx == fy) return 0;
        father[fx] = fy;
        return 1;
    }

    int makeConnected(int _n, vector<vector<int>>& connections) {
        int m = connections.size();
        n = _n;
        int groups = makeSet();
        for (int i = 0; i < m; i++) {
            groups - unionSet(connections[i][0], connections[i][1]);
        }
        if (groups > 1) return -1;
        return m - (n - 1);
    }
};

例二

P4003 [NOI2011]修建道路

题目描述：

小明所在的城市有n个交叉路口，它们之间有m条道路相连。如果两个路口之间有一条以上的道路相连，就认为它们之间的道路路况比较拥挤。现在小明受委托要对这些道路中的某些道路进行改造，以减少道路障碍，使得道路拥挤程度最低。

输入格式
第一行输入整数n，m，表示交叉路口数和道路条数。

接下来m行，每行输入两个整数x，y，表示x，y之间有一条双向的道路。

输出格式
一行输出一个整数，表示改造完毕后道路的拥挤程度。

数据范围
2≤n≤20000，
m≤100000

输入样例：
5 6
1 2
1 3
1 4
1 5
2 3
3 4
输出样例：
1

代码如下：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 20010, M = 100010;

int n, m;
int p[N], cnt[N];

struct Edge {
    int a, b;
}edges[M];

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

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

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

    for (int i = 0; i < m; i++) cin >> edges[i].a >> edges[i].b;

    int res = n;

    for (int i = 0; i < m; i++) {
        int a = edges[i].a, b = edges[i].b;
        if (find(a) != find(b)) {
            p[find(a)] = find(b);
            cnt[find(b)] += cnt[find(a)];
            res--;
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (p[i] == i) ans = max(ans, cnt[i]);
    }

    cout << res - ans << endl;

    return 0;
}

总结

并查集非常适用于组团和连通性问题，在$O(log_2n)$的时间复杂度内可以完成查找、合并两个集合、判断两个节点是否在同一个集合中的操作。在实现时，采用路径压缩的方法，可以大大提高并查集的效率。