并查集

并查集主要用于解决一些元素分组的问题, 它管理一系列的不相交的集合, 并且支持两种操作:

• 合并(Union): 把两个不相交的集合合并为一个集合
• 查询(find): 查询两个元素是否在同一个集合中

并查集的定义

并查集的重要思想在于, 用集合中一个元素代表集合, 在最初始的状态下, 每个元素作为独立的集合, 每个集合的代表元素都是自己. 所以我们可以初始化整个集合群如下:

初始化

const fa = [];
function init(int n)
{
    for (int i = 1; i <= n; ++i)
        // 每个元素的父节点的指向都是自己
        fa[i] = i;
}

查询

function find(x){
    if (fa[x] === x){
        // 到根节点了
        return x
    }else{
        return find(fa[x])
    }
}

当我们需要判断两个元素是否是同一个集合的时候, 只需要看他们的根节点是否相同就可以了.

合并

function merge(i, j)
{
    fa[find(i)] = find(j);
}

合并两个元素也很简单, 首先找到两个集合的代表元素, 然后将前者的父节点设置为后者就可以, 或者相反设置也是可以的.

路径压缩

最简单的并查集的效率是比较低的. 我们可以通过修改find写法,来把每个节点的父节点都设置为根节点, 来减少路径的长度:

function find(x){
    if(x === fa[x]){
        // 已经是根节点了
        return x
    }else{
        // 把父节点设置为根节点
        fa[x] = find(fa[x])
        // 返回这个父节点
        return fa[x]
    }
}

这里的代码我们可以简单的写成一行:

function find(x){
    return x == fa[x] ? x : (fa[x] = find(fa[x]))
}

对路径进行压缩以后, 并查集的时间复杂度就已经比较低了.

按秩合并

在上面的路径压缩优化以后, 并查集最终任然可能是一个比较复杂的树结构, 因为我们只在查询时进行优化, 并且也只优化一个路径.

更好的优化策略是在合并树的时候尽可能的把简单的树往复杂的树上面合并, 而不是相反的. 因此我们引入一个秩的概念.

我们用一个数组rank[]记录每个根节点对应的树的深度. 一开始, 把所有元素的rank(秩)设为1 , 合并的时候比较两个根节点, 把rank比较小的往比较大的上合并

路径合并和按秩合并如果一起使用, 时间复杂度接近O(n), 但是可能会破坏rank的准确性

初始化

function init(n) {
    for (let i = 0; i <= n; i++) {
        fa[i] = i
        rank[i] = 1   
    }
}

合并

function merge(i, j) {
    let x = find(i), y = find(j); // 先找到两个根节点
    if (rank[x] <= rank[y]){
        fa[x] = y
    }else {
        fa[y] = x
    }
    // 如果深度相同且根节点不同, 则新的根节点的深度 +1
    if(rank[x] == rank[y] && x != y){
        rank[y] ++;
    }
}