20.并查集

合并集合

#include <iostream>
#include <algorithm>

using namespace std;

int n,m;
const int N=1e5+10;
int father[N];

int find(int x)//查找x的祖先
{
    if(father[x]!=x) father[x]=find(father[x]);
//x不处于祖先位置时，递归调用查找x的祖先，每次返回时让当前节点的爹指向祖先
    return father[x];
}

int main()
{
    scanf("%d%d",&n,&m);
    
    for(int i=1;i<=n;i++)   father[i]=i;
    
    for(int i=1;i<=m;i++)
    {
        char s[2];
        int a,b;
        scanf("%s%d%d",s,&a,&b);
        if(s[0]=='M')
            father[find(a)]=find(b);
        else
        {
            if(find(a)==find(b))
                printf("Yes\n");
            else
                printf("No\n");
        }
    }
    return 0;
}

连通块中点的个数

#include <iostream>
#include <algorithm>

using namespace std;

const int N=1e5+10;

int n,m;
int father[N],Size[N];

int find(int x)
{
    if(x!=father[x]) father[x]=find(father[x]);
    return father[x];
}

int main()
{
    cin>>n>>m;
    
    for(int i=1;i<=n;i++)
    {
        father[i]=i;
        Size[i]=1;
    }
    
    for(int i=1;i<=m;i++)
    {
        char s[2];
        scanf("%s",s);
        if(s[0]=='C')
        {
            int a,b;
            scanf("%d%d",&a,&b);
            if(find(a)==find(b)) continue ;
            Size[find(b)]+=Size[find(a)];
            father[find(a)]=find(b);
        }
        else if(s[1]=='1')
        {
            int a,b;
            scanf("%d%d",&a,&b);
            if(find(a)==find(b))
                printf("Yes\n");
            else
                printf("No\n");
        }
        else if(s[1]=='2')
        {
            int a;
            scanf("%d",&a);
            printf("%d\n",Size[find(a)]);
        }
        
    }
    
    return 0;
}

食物链—集合模型

#include <iostream>
#include <algorithm>

using namespace std;

const int N=5e4+10,M=1e5+10;

int father[M],x[N*3+10],y[N*3+10];

void init()
{
    for(int i=0;i<=3*N;i++)
    {
        father[i]=i;
    }
}

int find(int x)
{
    if(father[x]!=x) father[x]=find(father[x]);
    return father[x];
}

void unite(int a,int b)
{
    int x=find(a);
    int y=find(b);
    if(x!=y)
    {
        father[y]=x;
    }
    
}
bool same(int x,int y)
{
    if(find(x)==find(y))
        return true;
    else
        return false;
}

int main()
{
    int n,k,ans;
    scanf("%d%d",&n,&k);
    init();
    for(int i=1;i<=k;i++)
    {
        int t,x,y;
        scanf("%d%d%d",&t,&x,&y);
        if(x<=0||x>n||y<=0||y>n)    
        {   
            ans++;
            continue;
        }
        if(t==1)//x和y是同类
        {
            if(same(x,y+N)||same(x,y+2*N))
                ans++;
            else
            {
                unite(x,y);
                unite(x+N,y+N);
                unite(x+2*N,y+2*N);
            }
        }
        else //x吃y
        {
            if(same(x,y)||same(x,y+2*N))
                ans++;
            else
            {
                unite(x,y+N);
                unite(x+N,y+2*N);
                unite(x+2*N,y);
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

解法二：带权并查集

并查集里面维护的关系，维护每个点到根节点的距离，把距离分成三大类，模3余0（与根节点同类），模三余1（可以吃根节点），模三余2（被根节点吃）,就不用在 n² 级别来判断

d[x]也会被伴随着路径压缩，因此
d[x]到根节点 = d[x]到父节点的距离 + 父节点到根节点的距离

#include<iostream>
using namespace std;
const int N=50010;
int n,k;
int p[N],d[N];//father、距离

int find(int x){
    if(p[x]!=x){
        int t=find(p[x]);
        d[x]+=d[p[x]];
        p[x]=t;
    } 
    return p[x];
}

int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        p[i]=i;
    }
    int res=0;
    while(k--){
        int t,x,y;
        scanf("%d%d%d",&t,&x,&y);
        if(x>n||y>n){
            res++;
        }else{
            int px=find(x),py=find(y);
            if(t==1){
                if(px==py&&(d[x]-d[y])%3!=0) res++;
                else if(px!=py){
                    p[px]=py;
                    d[px]=d[y]-d[x];
                }
            }
            else{
                if(px==py&&(d[x]-d[y]-1)%3!=0) res++;
                else if(px!=py){
                    p[px]=py;
                    d[px]=d[y]+1-d[x];
                }
            }
        }
    }
    cout<<res<<endl;
    return 0;
}