tags algos data-structure

三行并查集

并查集是一种简洁而优雅的数据结构，能够在O(1)的时间内实现对集合的查询和合并操作。

并查集的代码十分简洁，总共就三行

Init(n) { for(int i = 0; i < n; ++i) root[i] = i;}
Find(x) { return x == root[x] ? x : root[x] = find(root[x]); }
Union(x, y) {root[find(x)] = find(y); }

其中root[i]表示元素i的父节点

路径压缩

注意Find函数中使用的是递归调用, 其中将递归调用后得返回值重新赋值给root[x], 这是做法称为 路径压缩, 为了防止反复对集合进行合并后并查集退化成一条链，从而时间复杂度退化成线性时间所做的优化，注意无路径压缩的写法如下

x == root[x] ? x : find(root[x])

这c/c++用这种写法很OK，但是用python写，最少都要用两行

if root[x] != x: root[x] = find(root[x])
return root[x]

用下面的这种写法是不行的:

return x if root[x] == x else root[x] = find(root[x])

此外，路径压缩自然可以改写成非递归形式，做法很简单，下文略。

按秩归并

Union操作还可以进行按秩归并的优化. 首先介绍集合的rank的概念。 在并查集中，一个集合用一棵树表示，这棵树的深度就是该集合的rank，树越深rank越大. 容易知道rank越低find操作越高效，这也是路径压缩所追求的。按秩归并的思路是将rank低的集合并入到rank高的集合，这样可以延缓并查集变成一条链的情形，从而提高Find的效率. 若不是将小rank集合归如大rank结合，合并后的新集合的rank总会增长，最终rank=集合元素个数时，find操作是线性的。注意，为了实现按秩归并，我们仅需要多维护一个rank数组即可，足够简单。

加上了按秩归并优化的Union函数长成下面这个样子

void Union(x, y) {
    int xr = find(x), yr = find(y);
    if (rank[xr] <= rank[yr]) {
        root[xr] = yr;
        if (rank[xr] == rank[yr]) ++rank[yr];
    }
    else root[yr] = xr;

按秩归并算法多了几行，为了偷懒有时随便Union也OK. 不超时就好. 讲究一点的就按秩归并吧.

练习题

• leetcode 200
• leetcode 547
• leetcode 684
• leetcode 959
• leetcode 990

后续

可持久化并查集？等我学会了再写吧~~~