并查集简介

并查集（Disjoint-set data structure，直译为不交集数据结构）是一种常见的数据结构，一般用来处理一些不重复元素集合的合并以及查询问题。简单来说，就是给定一些元素，这些元素可以按照一定标准唯一的被划分到某个类别，而且在划分之后我们需要查询特定元素的类别。并查集可以高效的实现此类类别划分与查询问题。本文对并查集的算法和实现进行简要描述。

算法

并查集用一棵树表示一个集合，每一个树结点即是一个元素。每个结点保存着到它的父结点的引用，树的根结点通常保存到自身的引用以表示自身为根节点。根结点也被称为所在集合的代表元素。

既然名为“并查集”，那么其最重要的两个操作必然是合并（Union）和查询（Find）。

合并（Union）

“合并”是指合并两个集合。容易想到，如果要把集合 $A$ 合并到集合 $B$ 中，只需要找出集合 $A$ 的根结点 $Root_A$ 和集合 B 的根结点 $Root_B$，并将 $Root_A$ 的父结点设置为 $Root_B$ 即可。

查询（Find）

“查询”是指查找某个元素属于哪一个集合，也就是找到该元素所在结点的根结点。

实现

我们可以使用一个数组来实现当前结点到父结点的映射：

const parent: number[] = [];

当然，这里也可以使用 Map。其初始化也很简单，即每一个元素都自成集合：

function init(elementCount: number)
{
    for (let i = 0; i < elementCount; i++)
    {
        parent[i] = i;
    }
}

显然，并查集的初始化是一个 $O(n)$ 的操作。

查询

对于查询，给定一个元素的下标，返回其所在集合代表元素的下标：

function find(elementIndex: number): number
{
    let currentElementIndex = elementIndex;
    while (parent[currentElementIndex] !== currentElementIndex)
    {
        currentElementIndex = parent[currentElementIndex];
    }
    return currentElementIndex;
}

显然，以上的查询操作是一个 $O(n)$ 的操作。可以想到，如果所有元素都属于一个类别，查找将会很耗时。

那么，有没有办法优化查询操作呢？容易想到，我们在查找时只在乎根元素，不在乎每棵树长什么样子，因此我们可以进行路径压缩。

所谓路径压缩，就是使得每个元素到其类别根元素的查找路径为常数，这样查找的复杂度就可以降低到 $O(1)$。方法也很简单，添加一行代码即可：

function find(elementIndex: number): number
{
    let currentElementIndex = elementIndex;
    while (parent[currentElementIndex] !== currentElementIndex)
    {
        parent[currentElementIndex] = parent[parent[currentElementIndex]];    // 路径压缩
        currentElementIndex = parent[currentElementIndex];
    }
    return currentElementIndex;
}

从 while 循环来看这似乎还是一种 $O(n)$ 的算法，但实际上经过路径压缩之后其执行次数会大大降低。

路径压缩还有一种递归写法，可以进一步提升效率：

function find(elementIndex: number): number
{
    if (parent[elementIndex] !== elementIndex)
    {
        parent[elementIndex] = find(parent[elementIndex]);
    }
    return parent[elementIndex];
}

合并

对于合并，给定两个元素的下标，并对所在集合进行合并：

function union(fromElementIndex: number, toElementIndex: number)
{
    parent[find(fromElementIndex)] = find(toElementIndex);
}

封装

可以将以上代码合并成一个类并进行一些封装：

class UnionFindSet
{
    private readonly parent: number[];

    constructor(elementsCount: number)
    {
        this.parent = new Array(elementsCount);
        for (let i = 0; i < elementsCount; i++)
        {
            this.parent[i] = i;
        }
    }

    public find(elementIndex: number): number
    {
        if (this.parent[elementIndex] !== elementIndex)
        {
            this.parent[elementIndex] = this.find(parent[elementIndex]);
        }
        return this.parent[elementIndex];
    }

    public union(fromElementIndex: number, toElementIndex: number): void
    {
        this.parent[this.find(fromElementIndex)] = this.find(toElementIndex);
    }
}

应用

LeetCode 721 可以使用并查集来解决。该题目的解题思路是，合并邮箱到几个人名下，最后再整理输出即可。对应到并查集的概念里，邮箱就是元素，类别就是不同的人。

举例来说，给定输入 accounts：

[
    ["John","johnsmith@mail.com","john_newyork@mail.com"],
    ["John","johnsmith@mail.com","john00@mail.com"],
    ["Mary","mary@mail.com"],
    ["John","johnnybravo@mail.com"]
]

我们可以首先对人名和邮箱建立索引方便并查集运算，这可以通过三个 Map 实现：

虽然 johnsmith@mail.com 同时属于人名索引 1 和 2，但是根据题意 1 和 2 显然是同一个人，所以设置成谁是无所谓的。

然后我们就可以初始化并查集了。并查集有 5 个结点，代表 5 个邮箱：

根据 accounts[0]，合并 1 和 2：

根据 accounts[1]，合并 1 和 3：

accounts 后续都不涉及合并操作，因此我们得到了 1、4 和 5 三个类别代表元素索引，查表得到对应的人名索引分别是 1、3 和 4。因此我们就得到了以下的对应关系：

还原成邮箱和人名，我们就得到了答案：

整理一下输出，并对邮箱列表进行一次排序即可 AC。

修改记录

• 2022.5.2 添加了路径压缩相关内容。

参考文献

1. https://zh.wikipedia.org/wiki/%E5%B9%B6%E6%9F%A5%E9%9B%86
2. https://labuladong.gitee.io/algo/2/20/51/