并查集

目录

介绍

我们遇到一些有 \(n\) 个元素的集合应用问题中,当给出两个元素的一个无序对 \((a,b)\) 时,需要快速合并 \(a\) 和 \(b\) 分别所在的集合,并查集就是这样的用于处理分离集合的抽象数据类型。它的作用就是动态地维护和处理集合元素之间的复杂关系。

操作

使用并查集应首先记录一组分离的动态集合 \(S=\{S_1,S_2,...,S_k\}\),每个集合还要设置一个代表来识别,代表只要选择该集合中的某个元素(成员)即可,集合中的哪个元素被选作代表是无所谓的。并查集有三种操作:初始化、查找与合并。

这里的并查集采用树实现。树结构用静态数组模拟,设 fa[x] 表示 \(x\) 元素所指向的父亲。

1. 初始化

建立一个新的集合,其中仅有的成员是 \(x\),同时 \(x\) 也是代表。因为各集合是分离的,所以要求 \(x\) 没有在其他集合中出现过。使用并查集之前都需要执行一次初始化操作。树结构并查集初始化操作的实现很简单,只需要执行 fa[x]=x 即可。

for(int i=1;i<=n;++i) fa[i]=i;
2. 查找

查找一个元素所在的集合,这个操作返回该集合的代表,也就是树根。查找操作是并查集的核心操作,也是优化并查集效率的重点。

对于树结构,查找时需要以 \(x\) 为基点,向上寻找它的父结点,再以父节点为基点,向上寻找父节点的父节点……直到找到根结点为止。

路径压缩:在查找一个结点所在树的根结点的过程中,一条从待查结点到根结点的路径。我们不妨让这些路径上的结点直接指向根结点,即作为根结点的子节点。这样,这些路径上的结点仍在分离集合中,整棵树仍然满足分离集合树的要求,但是路径上结点的深度就减小了。这就是路径压缩。

ll fin(ll x)//路径压缩
{
    if(fa[x]!=x) fa[x]=fin(fa[x]);
    return fa[x];
    
    /* 上下两种写法等价
    if(fa[x]==x) return x;
    else return fa[x]=fin(fa[x]);
    */
}

我们看到,查找过程是一个递归的过程,实现非常简洁。同时,我们的方法也可以保证递归深度不会很深。

3. 合并

合并即把两个集合合并成一个集合。一般来说,在不同的实现中通常都以 \(S_x\) 或者 \(S_y\) 的代表作为新集合的代表。合并之前先判断两个元素是否属于同一集合,这个可以通过查找来实现。

void merge(ll x,ll y)
{
    x=find(x);
    y=find(y);
    fa[y]=x;
}

按秩合并:使得树拥有比较小的深度。我们可以用结点数(称为“秩”,rank)代替树的深度进行比较。

void merge(ll x,ll y) //按秩合并
{
    x=find(x);
    y=find(y);
    if(x==y) return;
    if(ran[x]<ran[y])
        fa[x]=y;
    else
    {
        fa[y]=x;
        if(ran[x]==ran[y])
            ran[x]++;
    }
}

如果将路径压缩和按秩合并一起使用,则可以证明,\(n\) 次查找最多需要用 \(O(n*\alpha(n))\) 的时间,其中 \(\alpha(n)\) 是单变量阿克曼函数的逆函数,它是一个增长速度比 \(\log_2n\) 慢得多但又不是常数的函数。在一般情况下 \(\alpha(n) \leq 4\),可以当作常数。

相关习题

1. 亲戚

luoguP1551(数据弱)

一本通1346(数据强)

这道题是一个并查集的模板题,对于较弱的数据,查找过程中只需要用路径压缩即可。对于较强的数据,既要路径压缩还要按秩合并,甚至还需要快读和卡常优化(不是)

对于一本通的题目描述,Code:

#include<头文件>
using namespace std;
typedef long long ll;

inline ll read(){
    快读;
}

ll ans=0;
ll fa[50002],ran[50002];

void start(ll n)//初始化
{
    for(int i=1;i<=n;++i)
    {
        fa[i]=i;
        ran[i]=0;
    }
}

ll fin(ll x)//查找-路径压缩
{
    if(fa[x]!=x) fa[x]=fin(fa[x]);
    return fa[x];
    // if(fa[x]==x) return x;
    // else return fa[x]=fin(fa[x]);
}

void merge(ll x,ll y)//按秩合并
{
    if(x==y) return;
    if(ran[x]<ran[y])
        fa[x]=y;
    else
    {
        fa[y]=x;
        if(ran[x]==ran[y])
            ran[x]++;
    }
}

int main()
{
    ll n,m,p;
    n=read();
    m=read();
    start(n); //初始化
    for(int i=1;i<=m;++i) //合并
    {
        ll x,y;
        x=read();
        y=read();
        ll fax=fin(x);
        ll fay=fin(y);
        merge(fax,fay);
    }
    p=read();
    for(int i=1;i<=p;++i) //询问
    {
        ll x,y;
        x=read();
        y=read();
        if( fin(x) == fin(y) )
            puts("Yes");
        else puts("No");
    }
    return 0;
}

2. 家谱

luoguP2814

一本通1388

巧妙使用STL的 map,把结点和它的父亲直接连接起来即可。

Code:

#include<头文件>
using namespace std;
typedef long long ll;

inline ll read()

map<string,string> fa;

string fin(string x) //路径压缩
{
    if(x!=fa[x]) fa[x]=fin(fa[x]);
    return fa[x];
}

string s,s1;

int main()
{
    char ch;
    cin>>ch;
    while(ch!='$')
    {
        cin>>s;
        if(ch=='#')
        {
            s1=s;
            if(fa[s]=="") //自己的父亲是自己(没有修改过)
            fa[s]=s; //设为真正的自己
            //否则不更改
        }
        else if(ch=='+')
            fa[s]=s1;
        else
            cout<<s<<" "<<fin(s)<<endl;
        cin>>ch;
    }    
    return 0;
}
3. 食物链

luoguP2024

一本通1390

本题中一共有3种动物,我们给每个动物一个权值,同一类的动物对于3取余。

我们发现这样一个特性:如果知道A与B的关系、B与C的关系,那么可以推出A和C的关系。也就是说。对于已知相互关系的动物集合 \(S_1,S_2\),我们只要直到其中 \(a\) 属于 \(S_1\),\(b\) 属于 \(S_2\) ,那么 \(S_1,S_2\) 中任意两个元素的关系就可以推出来了。由此,我们可以使用带权的并查集来维护它们之间的关系。

Code:

#include <头文件>
using namespace std;
typedef long long ll;

inline ll read()

ll n, k, x, y, d, ans;
ll fa[100002], ran[100002];

void start(int n) //初始化
{
    for (int i = 1; i <= n; ++i)
        fa[i] = i;
}

ll fin(ll x) //查找+路径压缩
{
    if (x != fa[x])
    {
        ll tmp = fa[x];
        fa[x] = fin(fa[x]);
        ran[x] = (ran[x] + ran[tmp]) % 3;
    }
    return fa[x];
}

int main()
{
    n = read();
    k = read();
    start(n); //初始化

    for (int i = 1; i <= k; ++i)
    {
        d = read();
        x = read();
        y = read();
        if (x > n or y > n) //第一种不符合条件的情况
        {
            ++ans;
            continue;
        }
        if (d == 1)
        {
            if (fin(x) == fin(y))
            {
                if (ran[x] != ran[y]) 
                    ++ans;
            }
            else
            {
                {
                    ran[fa[x]] = (ran[y] - ran[x] + 3) % 3;
                    fa[fa[x]] = fa[y];
                }
            }
        }
        else
        {
            if (x == y) //自己吃自己
            {
                ++ans;
                continue;
            }
            if (fin(x) == fin(y))
            {
                if (ran[x] != (ran[y] + 1) % 3) //与前面冲突
                    ++ans;
            }
            else
            {
                ran[fa[x]] = (ran[y] - ran[x] + 4) % 3;
                fa[fa[x]] = fa[y];
            }
        }
    }
    
    printf("%lld\n", ans);
    return 0;
}

EdisonBa

2021.2.2 初次编辑

上一篇:网络编程0:网络基础知识


下一篇:tcp与udp