算法图算法

并查集

字数统计: 1.9k字   |   阅读时长: 7分
, , , ,

摘要: 并查集的原理与代码模板

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文介绍并查集的原理和代码模板，最后针对并查集可以解决的几类问题，列出了一些题目列表。

$1 并查集

并查集是一种可以动态维护若干个不重叠的集合，并支持合并与查询的数据结构。它包含两个基本操作：

  • 查询 find(x)，查询一个元素属于哪个集合。
  • 合并 union(x, y)，把两个集合合并为一个集合。

集合的表示

在并查集中，我们用代表元的方法表示集合。也就是为每个集合选一个固定的元素，称其为代表元，作为整个集合的代表。

归属关系的表示

如果用数组，vec[x] 表示元素 x 所在集合的代表，那么可与快速查询元素的所属集合，但是合并时需要大量修改 vec 中的值。

如果用树形结构存储集合，树上的每个节点都是一个元素，树根为集合的代表元。则并查集是一个森林，此时我们仍然可以用数组维护这个森林。fa[x] 表示 x 的父节点，若 x 为根节点，则 fa[x] = x。

基本操作

并查集支持合并和查询两个操作。下面我们看一下用森林维护并查集时，这两种操作具体是怎么做的。

在用 find(x) 查询 x 属于哪个集合时，需要从该元素开始，通过 fa 不断递归地访问父节点，直至到达树根，返回树根编号作为所属集合的 id。

用森林维护并查集时，合并操作 union(x, y) 只需要连接两个树根即可，也就是 fa[find(x)] = find(y)。

为了提高查询效率，并查集可以引入路径压缩和按秩合并两种思想。

路径压缩

每次 find(x) 时，向上查找过程中会经过一些节点，把这些节点的父节点都设为 find(x) 找到的根，以后的查找再经过这个点的时候就可以一次找到根。

1
2
3
4
5
6
7
int _find(int x)
{
    if(_father[x] == x)
        return x;
    else
        return _father[x] = _find(_father[x]); // 路径压缩
}

按秩合并

额外维护一个 rank 数组，rank[x] 表示以 x 为根的子树的高度，合并时把较矮的树的树根连接到较高的树的树根上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void merge(int x, int y)
{
    x = _find(x);
    y = _find(y);
    if(x == y) return;

    // 此时 x, y 是所在树的根
    if(_rank[x] < _rank[y])
        _father[x] = y;
    else
    {
        _father[y] = x;
        if(_rank[x] == _rank[y])
            ++_rank[x];
    }
}

也可以把秩定义为以 x 为根的子树的大小，此时按秩合并也称为启发式合并。这种思想在很多数据结构中都有应用，也就是把小的结构合并到大的结构中，只增加小的结构的查询代价。

使用路径压缩的并查集，查询的时间复杂度为摊销 $O(\log N)$，使用按秩合并的并查集，查询的时间复杂度为 $O(\log N)$，同时使用路径压缩和按秩合并的并查集，查询的时间复杂度为摊销 $O(\alpha (N))$，其中 $O(\alpha (N))$ 为反阿克曼函数，在 1975 年 R.E.Tarjan 的论文 《Efficiency of a Good But Not Linear Set Union Algorithm》 中给出了证明。

并查集解决的问题

并查集可以解决图上的以下问题：

  • 加边连通性：不断加边，同时问某两个点是否连通。
  • Kruskal 最小生成树
  • 连通分量：个数，大小
  • 环：判定，长度，个数

$2 模板题：547. 省份数量

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 $n \times n$ 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中 省份 的数量。

提示：

1
2
3
4
5
6
1 <= n <= 200
n == isConnected.length
n == isConnected[i].length
isConnected[i][j] 为 1 或 0
isConnected[i][i] == 1
isConnected[i][j] == isConnected[j][i]

示例 1：
输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2
示例 2：
输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出：3

代码 (C++，模板)

连通分量个数，内部用 _set_size 维护连通分量个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class UnionFindSet {
public:
    UnionFindSet(int n)
    {
        _set_size = n;
        _father = vector<int>(n, -1);
        _rank = vector<int>(n, 0);
        for(int i = 0; i < n; ++i)
            _father[i] = i;
    }

    ~UnionFindSet(){}

    bool same(int x, int y)
    {
        return _find(x) == _find(y);
    }

    void merge(int x, int y)
    {
        x = _find(x);
        y = _find(y);
        if(x == y) return;

        // 此时 x, y 是所在树的根
        if(_rank[x] < _rank[y])
            _father[x] = y;
        else
        {
            _father[y] = x;
            if(_rank[x] == _rank[y])
                ++_rank[x];
        }

        --_set_size;
    }

    int set_size()
    {
        return _set_size;
    }

private:
    vector<int> _father;
    vector<int> _rank;
    int _set_size;

    int _find(int x)
    {
        if(_father[x] == x)
            return x;
        else
            return _father[x] = _find(_father[x]); // 路径压缩
    }
};

class Solution {
public:
    int findCircleNum(vector<vector<int>>& M) {
        int m = M.size();
        if(m == 1) return 1;
        UnionFindSet unionfindset(m);
        for(int i = 0; i < m - 1; ++i)
            for(int j = i + 1; j < m; ++j)
                if(M[i][j] == 1)
                    unionfindset.merge(i, j);
        return unionfindset.set_size();
    }
};

$3 并查集的回滚

如果并查集要支持回滚操作，就是要把已经合并成一棵树的若干子树，恢复成此前的若干子树。需要开栈保存每次合并操作时，被合并的哪一个根(高度较小的那一个根)。后续通过栈里的信息回滚。

支持回滚操作就不能使用路径压缩了，因为路径压缩回改变节点与节点之间的关系。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
stack<int> st; // 保存每次合并操作时被合并的根

void merge(int x, int y)
{
    x = _find(x);
    y = _find(y);
    if(x == y) return;
    // 此时 x, y 是所在树的根
    if(_rank[x] < _rank[y])
    {
        _father[x] = y;
        st.push(x); // x 被合并
    }
    else
    {
        _father[y] = x;
        if(_rank[x] == _rank[y])
            ++_rank[x];
        st.push(y); // y 被合并
    }
    --_set_size;
}

$4 题目汇总

(1) 加边连通性

不断加边，同时问某两个点是否连通。可以动态维护具有传递性的关系。

(2) Kruskal

(3) 连通分量

解决连通分量的判定、个数、属性、大小相关的问题。

连通分量判定

连通分量个数

连通分量属性

连通分量大小

(4) 环

解决环的判定、长度、大小相关的问题。

Share