概念和基本操作

将一个含有不同元素的大集合看作是其若干个不相交的子集的并，是一种常见的方法。并查集（Disjoint set）就是用来表示这种不交并的数据结构。其中每个子集都用一个元素来作为其代表元。有点类似于等价类的概念。几个基本的操作包括：

1. make_set:初始化建立只含一个元素的集合；
2. union_set:将两个集合合并；
3. fnd_set:求得给定集合的代表元。

数据结构实现

可以使用链表和树来实现并查集。我们这里使用树结构。即每个子集的元素形成一棵树，根节点就是代表元，各个子集就形成了一个森林，从而表示整个并查集。find_set只需要返回根节点，而union_set只需要将一棵树的根节点指向另一棵树的根节点。

优化

并查集的优化主要有两点启发式的策略：

• 按序归并（union by rank）：因为find_set需要返回根节点，所以平均查找路径越短越好，即各个子树的高度尽量平衡。所以在union_set时，可将高度低的连接到高度高的子树上。具体实现时，不一定非要使用精确的高度，而往往使用高度的一个上界。具体可以参考下面的代码。
• 路径压缩（path compression）：因为在并查集的操作中，我们只关心元素所属的集合（等价类），所以在查找一个元素所在树的根节点的过程中，可以把查找路径上的所有元素都直接指向根节点，这样在下次find_set时，查找的高度自然就降低了。

算法复杂度

这里只列出使用上述启发策略后，并查集算法的时间复杂度结果。对证明感兴趣的同学可以去查阅算法导论。

如果设初始大集合有\(n\)个不同的元素，一共进行了\(m\)次相关的并查集操作，则时间复杂度为\(O(m\cdot a(n))\)，其中\(a(n)\)是一个增长很慢的函数，实际中多数情况下可以认为\(a(n)\le 4\)。

例子

感兴趣的同学可以使用 poj1611 作为并查集的基础练习。

这里给出基本操作的代码作为参考：

//p[x]为x的父节点
//rank[x]为上面说的高度的一个上界函数

int make_set(int x) {
    p[x] = x;
    rank[x] = 0;
    return 0;
}

int union_set(int x,int y) {
    x = find_set(x);
    y = find_set(y);
    if (rank[x] > rank[y])
        p[y] = x;
    else {
        p[x] = y;
        if (rank[x] == rank[y])
            ++rank[y];
    }
    return 0;
}

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

参考文献：

算法导论 Chapter 21 Data Structures for Disjoint Sets>