并查集

灯珑LoGin

发布于 2022-10-31 12:34:00

6570

发布于 2022-10-31 12:34:00

文章被收录于专栏：龙进的专栏

并查集是一种用互质的集合对数据进行分类管理的数据结构。

并查集主要实现了两个功能：合并与查询

我们用一个数组fa[i]来表示第i个元素所在集合的根节点。

根节点的父节点指向它自身。

初始的时候，我们把fa[i]=i，这样就初始化了n个互质的集合。

然后当要合并两个节点x、y所在的集合的时候，就先找到他们的根节点（代表元），然后将一个集合的根节点指向另一个节点的根节点即可。

判断两个元素所在集合是否相同，其实就是去找他们所在集合的代表元。代表元相同，那么就证明这两个元素在同一个集合里面。

对于题目 DSL_1_A 来说，题目要求实现一个简单的并查集，代码如下：

#include<iostream>
#include<string.h>
using namespace std;

#define MAXN 10005

int fa[MAXN];
int n;

int find_root(int x)
{
    if(fa[x]==x)
        return x;
    
    return find_root(fa[x]);
    
}


void unite(int x,int y)
{
    fa[find_root(x)] = find_root(y);
}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n;
    for(int i=0;i<n;++i)
    {
        fa[i] = i;
    }

    int q;
    cin>>q;

    int com,x,y;
    for(int i=0;i<q;++i)
    {
        cin>>com>>x>>y;
        if(com==0)
        {
            unite(x,y);
        }
        else
        {
            cout<<(find_root(x)==find_root(y)?1:0)<<endl;
        }
        
    }
    
}

对于上面这个题目，我们会发现，运行的状况是这样的

这虽然是AC了，可是耗时有点高啊，耗时0.4s，n的数据范围是10000，操作数最大为100000。这怎么看都不像一个时间复杂度低于O(logn)的算法啊。

那么肯定是有优化空间的。

路径压缩

但是，这样子的话，每次查找都需要递归很多次，非常的费时。我们就可以在合并集合的时候，做路径压缩来解决这个问题。

路径压缩就是，把一个集合里面，正在合并的节点都的父节点都指向合并时的根节点。这样使得路径得到了压缩，减少了查询的耗时。

怎么说吧，我觉得路径压缩有点动态规划的思想在里面，就是每次查询找到当前节点的根节点之后，就更新进去fa数组，然后下次用到这个值的时候，就可以减少调用的次数了。

代码实现如下：

int find_root(int x)
{
    if(fa[x]==x)
        return x;
    
    int t = find_root(fa[x]);
    fa[x] = t;
    return t;
    
}

按秩合并

并查集的按秩合并说白了就是把高度矮的树合并到高度高的树上。

按秩合并能显著降低最长路径长度，这样的话，在查询的时候可以更快地查询到根节点。只有使用了路径压缩+按秩合并的并查集，时间复杂度才会低于O(logn)

我们需要使用一个数组Rank[i]来存储第i个节点作为根节点时，它的树的高度。

那么我们发现，需要更新Rank[i]的情况只有是在合并集合且两个集合树高相等时，才需要把一个集合的根节点的树高+1。

具体的代码实现就是，初始化一个全局数组Rank[i]，把它的值都设为0，接着，把合并集合的函数改成下面这样：

void unite(int x,int y)
{
    int fx = find_root(x);
    int fy = find_root(y);

    if(Rank[fx]>Rank[fy])
    {
        fa[fy] = fx;
    }
    else
    {
        fa[fx] = fy;
        if(Rank[fx]==Rank[fy])
            Rank[fy]++;
    }

}

再把代码提交上去，可以发现，运行时间减少到了0.05s，这差不多加速了10倍啊！