客户端基本不用的算法系列：并查集算法介绍（union-find）

并查集算法（union-find）

接受了大家的反馈，决定将之前的图论告一段落，我在基础的数据结构和数据处理的场景下找一些好玩的算法来写写。这些东西会极大的帮助你的面试，在那些需要考算法的大厂运用这些知识来解题是十分加分的。

在 LeetCode 上有一道题 LeetCode-547 朋友圈[1]，题目大意是这样：

班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。

这题最后让我们求得集合数。其实无论在工作中还是在生活中，这种分组问题十分常见。我们当然可以把每一类东西往一个 Array 或者是 Set 中塞入，然后不断的去搜每一个集合是否有关联进而合并组，最终也可求得分组数。但是拍脑袋想，我们要遍历 N 次每个集合，真的是一个超级耗时的办法。

那么有什么更加优美的数据结构来解决这类问题呢？其实就是今天要讲的并查集（union-find）。

并查集是什么？

并查集是用来管理元素分组状况的数据结构。并查集可以高效地执行如下操作。不过需要注意并查集虽然可以进行合并操作，但是无法进行分割操作。

•查询元素 a 和元素 b 是否属于同一组•合并 a 和 b 所在的组

并查集的结构

使用树形结构来实现，但不是二叉树。

每个元素对应一个节点，每个组对应一棵树。在并查集中，哪个节点是哪个节点的父亲以及树的形状信息无需多加关注，树形结构这个整体才是最重要的。

1. 初始化

我们准备 n 个节点来表示 n 个元素，最开始没有边。

2. 合并

例如下图，从一个组的根向另一个组的根相连，这样两棵树就变成了一棵树，也就把两个组合并为一个组了。

其实我们发现合并并没有一个固定的规律，只要将两棵不规则树合起来就好。

3. 查询

为了查询两个节点是否属于同一个组，我们需要沿着树向上走，来查询包含这个元素的树的根是谁。如果两个节点走到了同一根，那么就说明它们属于同一组。

例如下图中，元素 2 和元素 5 都走到了元素 1，因此它们属于同一组。另一方面，由于元素 7 走到的是元素 6 ，因此同元素 2 或元素 5 属于不同组。

实现

好了，这种场景我们需要怎样实现呢？是否需要一个复杂的树来做呢？其实不用，请记住：虽然我们的思路是通过树型结构来解决，但是代码实现永远不要局限于思路。类似于二叉树，我们同样的也可以通过一维数组来实现，并查集也是如此。

#include <iostream>
using namespace std;

int id[100000];
int cnt = 0;

int find(int p) {
    while (p != id[p]) {
        p = id[p];
    }
    return p;
}

void unio(int p, int q) {
    int rp = find(p);
    int rq = find(q);
    if (rp == rq) return;
    id[rp] = rq;
    cnt --;
}

int main() {
    cnt = 7;

    for (int i = 0; i < cnt; ++ i) {
        id[i] = i;
    }

    unio(0, 1);
    unio(1, 4);
    unio(5, 3);
    unio(3, 6);

    cout << cnt << endl; // 3 个集合

    cout << "0 的根" << find(0) << endl; // 0 的根4
    cout << "1 的根" << find(1) << endl; // 1 的根4
    cout << "2 的根" << find(2) << endl; // 2 的根2
    cout << "3 的根" << find(3) << endl; // 3 的根6
    cout << "4 的根" << find(4) << endl; // 4 的根4
    cout << "5 的根" << find(5) << endl; // 5 的根6
    cout << "6 的根" << find(6) << endl; // 6 的根6
    return 0;
}

这里有一张动图，大家点击原文查看一下。

复杂度

通过上图，我们不难看出，这棵数的深度可能会越来越深。在对于 find 来说，可能会带来较大的性能消耗，while 循环次数增多。此时 union 操作主要依赖于 find 操作，而 find 操作的时间复杂度取决于这棵树的深度。所以查询和合并操作都是 O(m)。

倘若我们有方法减少树的深度，是不是就能让时间开销大幅度减少了？是的，请看下期《并查集的 Rank 秩优化》。

References

[1] LeetCode-547 朋友圈: https://leetcode-cn.com/problems/friend-circles/