并查集

oneNeko 于 2021-05-14 发布

并查集主要用于解决一些元素分组的问题。它管理一系列不相交的集合,并支持两种操作:
合并(Union):把两个不相交的集合合并为一个集合。
查询(Find):查询两个元素是否在同一个集合中。 并查集最直接的一个应用场景便是亲戚问题

并查集基本结构

// 初始化。
// 使用fa数组表示父亲节点,初始化时将父亲节点设置为自身
int fa[MAXN];
inline void init(int n)
{
    for (int i = 1; i <= n; ++i)
        fa[i] = i;
}

// 查询
// 找到根节点,根节点的父节点就是自己。
// 要判断两个元素是否属于同一个集合,只需要看它们的根节点是否相同即可。
int find(int x)
{
    if(fa[x] == x)
        return x;
    else
        return find(fa[x]);
}

// 合并
// 先找到两个集合的代表元素,然后将前者的父节点设为后者即可
void merge(int i, int j)
{
    fa[find(i)] = find(j);
}

合并(路径压缩)

最简单的并查集效率是比较低的。因为可能会形成一条长长的链,随着链越来越长,我们想要从底部找到根节点会变得越来越难。
怎么解决呢?我们可以使用路径压缩的方法。既然我们只关心一个元素对应的根节点,那我们希望每个元素到根节点的路径尽可能短,
只要我们在查询的过程中,把沿途的每个节点的父节点都设为根节点即可。下一次再查询时,我们就可以省很多事。这用递归的写法很容易实现:

int find(int x)
{
    if(x == fa[x])
        return x;
    else{
        fa[x] = find(fa[x]);  //父节点设为根节点
        return fa[x];         //返回父节点
    }
}

// 简写
int find(int x)
{
    return x == fa[x] ? x : (fa[x] = find(fa[x]));
}

按秩合并

有些人可能有一个误解,以为路径压缩优化后,并查集始终都是一个菊花图(只有两层的树的俗称)。但其实,由于路径压缩只在查询时进行,也只压缩一条路径,所以并查集最终的结构仍然可能是比较复杂的。
我们用一个数组rank[]记录每个根节点对应的树的深度(如果不是根节点,其rank相当于以它作为根节点的子树的深度)。一开始,把所有元素的rank(秩)设为1。合并时比较两个根节点,把rank较小者往较大者上合并。 路径压缩和按秩合并如果一起使用,时间复杂度接近 o(n),但是很可能会破坏rank的准确性。

初始化(按秩合并)

inline void init(int n)
{
    for (int i = 1; i <= n; ++i)
    {
        fa[i] = i;
        rank[i] = 1;
    }
}

合并(按秩合并)

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

参考

https://zhuanlan.zhihu.com/p/93647900/