并查集

Author Avatar
Axell 8月 25, 2018
  • 在其它设备中阅读本文章

并查集

用来确定点之间的关系

代码实现

变量初始化

int a[MAXN],f[MAXN]; //a[]可用来存放数据/权值

初始化(init)

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

查找根节点(getroot)

int getroot(int x){
    if (f[x]==x) return x;
    f[x]=getroot(f[x]);
    return f[x];
}

合并(add)

void add(int x,int y){
    int t1=getroot(x);
    int t2=getroot(y);
    if (t1==t2) return;
    f[t1]=t2;
    a[t2]+=a[t1];  //可以更改这里的操作
}

例题

题目描述

若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的某个人所在家族的人数。
规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。

输入

第一行：三个整数n，（n<=100,000,m<=200,000），分别表示有n个人，m个信息。
以下m行：信息包含两种形式：
M a b：表示a和b具有亲戚关系。
Q a：要求输出a所在家族的人数。

输出

要求输出a所在家族的人数。

样例输入

5 10
M 3 2
Q 4
M 1 2
Q 4
M 3 2
Q 1
M 3 1
Q 5
M 4 2
Q 4

样例输出

1
1
3
1
4

代码

#include <bits/stdc++.h>
using namespace std;

int a[100005],f[100005],n,m;
char tmp;

int getroot(int x){
    if (f[x]==x) return x;
    f[x]=getroot(f[x]);
    return f[x];
}

void add(int x,int y){
    int t1=getroot(x);
    int t2=getroot(y);
    if (t1==t2) return;
    f[t1]=t2;
    a[t2]+=a[t1];
}

int get(int x){
    int te=getroot(x);
    return a[te];
}

int main(){
    cin>>n>>m;
    for (int i=1;i<=n;++i)
        f[i]=i,a[i]=1;
    for (int i=1;i<=m;++i){
        tmp=getchar();
        while (tmp!='M'&&tmp!='Q') tmp=getchar();
        if (tmp=='M') {
            int g,b;
            scanf("%d %d",&g,&b);
            add(g,b);
        }else{
            int g;
            scanf("%d",&g);
            printf("%d\n",get(g));
        }
    }
    return 0;
}

关系并查集

处理两者之间的关系的并查集
常见的题目: 食物链
实现方式: 将权值设定为与根节点的距离(%p),根据权值之差(%p)判断关系

食物链

题目描述

动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。
现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这N个动物所构成的食物链关系进行描述：
第一种说法是”1 X Y”，表示X和Y是同类。
第二种说法是”2 X Y”，表示X吃Y。
此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

1） 当前的话与前面的某些真的话冲突，就是假话；
2） 当前的话中X或Y比N大，就是假话；
3） 当前的话表示X吃X，就是假话。

你的任务是根据给定的N（1 <= N <= 50,000）和K句话（0 <= K <= 100,000），输出假话的总数。

输入

第一行是两个整数N和K，以一个空格分隔。
以下K行每行是三个正整数D，X，Y，两数之间用一个空格隔开，其中 D 表示说法的种类。
若D=1，则表示X和Y是同类。
若D=2，则表示X吃Y。

输出

只有一个整数，表示假话的数目。

样例输入
100 7
1 101 1
2 1 2
2 2 3
2 3 3 
1 1 3
2 3 1
1 5 5
样例输出
3
思路

本题要将动物分成 3 类，看似要 3 个集合，无法用并查集做。但如果我们在三类关系间引入相对距离（偏移量），判断两个动物相对距离的关系，就能确定 2 个动物的食物链。
三类动物的相对距离为 0，1，2，令 0 吃 1，1 吃 2，2 吃 0，从数值上，我们发现如果 a
吃 b，那么(a-b+3)%3=2。由此, 我们对于“同类”和“吃”两种操作，还是可以利用并
查集合并，具体有：

  1. 如果 a, b 同类，我们首先判断 a,b 是属于同一集合（是否有相对关系），如果属
    于同一集合，就可判断是否是假话；否则，就要合并 a,b，令 u,v 分别为 a,b 的父亲，不

失一般性，我们可以让 b 的父亲 v 合并到 a 上面，现在问题就是 v 到 a 的距离定义为多少。
令 dis[b]表示 b 到父亲 v 的距离，而最终 b 和 a 要是同类，那么 b 到 a 的距离
(dis[b]+dis[v])%3=0，即 dis[v]=3-dis[b]。

  1. 如果 a 吃 b,我们也要先判断 a,b 是否属于同一集合，如果属于同一集合，就可以
    判断真假；否则，也需要合并 a,b，让 a,b 产生相对距离。令 u,v 分别为 a,b 的父亲，同

上面的方法，v 合并到 a，b 到 a 的距离(0-(dis[b]+dis[v])+3)%3=2, 即 dis[v]=
(1-dis[b]+3)%3。

剩下的问题，就是如何维护 dis 数组。在 x 点找父亲过程中，x 的父亲会不断变化，直到
遇到最终的父亲，那么 dis[x]也就一直需要跟着变化。但其实，我们发现在递归找 x 父亲的时候，x 原父亲 y 离最终父亲的距离能计算出来，那么 x 与最终父亲的距离就为
(dis[x]+dis[y])%3，至此所有问题可以解决，具体实现参考如下代码。

代码
#include <bits/stdc++.h>
using namespace std;

int f[50005],v[50005],n,m,ans;

int getroot(int x){
    if (f[x]==x) return x;
    int tmp=f[x];
    f[x]=getroot(f[x]);
    v[x]=(v[x]+v[tmp])%3;  //路径压缩
    return f[x];
}

void add(int x,int y,int len){
    int t1=getroot(x);
    int t2=getroot(y);
    if (t1==t2){
        return;
    }
    f[t1]=t2;
    v[t1]=(v[y]+len-v[x])%3;  //要维持他们之间的关系
}

bool check(int len,int x,int y){
    if (x>n||y>n) return false;
    if (len==1&&x==y) return false;
    if (getroot(x)==getroot(y))
        return ((v[x]-v[y])%3+3)%3==len;  //判断关系
    return true; //如果关系未知,返回true
}

int main(){
    cin>>n>>m;
    for (int i=1;i<=n;++i)
        f[i]=i;
    for (int i=1;i<=m;++i){
        int len,x,y;   //len==0 a==b,len==1 a>b,len==2 a<b
        scanf("%d %d %d",&len,&x,&y);
        len--;         //!!len==0表示同类
        if (check(len,x,y)){
            add(x,y,len);
        }else{
            ans++;
        }
    }
    cout<<ans;
    return 0;
}

知识共享许可协议
本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/10/