C124 扩展域并查集 P2024 [NOI2001] 食物链
C125【模板】带权并查集 P2024 [NOI2001] 食物链

#include<bits/stdc++.h>
using namespace std;
int fa[160000];
int findfa(int x){return fa[x]=(fa[x]==x)?fa[x]:findfa(fa[x]);}
//每只动物都有三个分身（0号，1号，2号）， 0号吃1号，1号吃2号，2号吃0号
//所有动物的0号分身在位置    1 ~   n
//所有动物的1号分身在位置  n+1 ~ 2*n
//所有动物的2号分身在位置2*n+1 ~ 3*n
int main()
{
    int n,k;scanf("%d%d",&n,&k);
    for(int i=1;i<=3*n;i++)fa[i]=i;
    int ans=0,tx0,ty0,tx1,ty1,tx2,ty2,c,x,y;
    for(int i=1;i<=k;i++)
    {
        scanf("%d%d%d",&c,&x,&y);
        if(x>n || y>n){ans++;continue;}
        if(c==2 && x==y){ans++;continue;}
        tx0=findfa(x);ty0=findfa(y);
        tx1=findfa(x+n);ty1=findfa(y+n);
        tx2=findfa(x+2*n);ty2=findfa(y+2*n);
        if(c==1)
        {
            if( tx0==ty1 || tx0==ty2 )ans++;
            else fa[tx0]=ty0,
                 fa[tx1]=ty1,
                 fa[tx2]=ty2;
        }
        else
        {
            if( tx0==ty0 || tx0==ty1 )ans++;
            else fa[tx0]=ty2,
                 fa[tx1]=ty0,
                 fa[tx2]=ty1;
        }
    }
    printf("%d\n",ans);
    return 0;
}

C124 扩展域并查集 P2024 [NOI2001] 食物链
C125【模板】带权并查集 P2024 [NOI2001] 食物链

#include<bits/stdc++.h>
using namespace std;
int fa[160000];
int findfa(int x){return fa[x]=(fa[x]==x)?fa[x]:findfa(fa[x]);}
//每只动物都有三个分身（0号，1号，2号）， 0号吃1号，1号吃2号，2号吃0号
//所有动物的0号分身在位置    1 ~   n
//所有动物的1号分身在位置  n+1 ~ 2*n
//所有动物的2号分身在位置2*n+1 ~ 3*n
int main()
{
    int n,k;scanf("%d%d",&n,&k);
    for(int i=1;i<=3*n;i++)fa[i]=i;
    int ans=0,tx0,ty0,tx1,ty1,tx2,ty2,c,x,y;
    for(int i=1;i<=k;i++)
    {
        scanf("%d%d%d",&c,&x,&y);
        if(x>n || y>n){ans++;continue;}
        if(c==2 && x==y){ans++;continue;}
        tx0=findfa(x);ty0=findfa(y);
        tx1=findfa(x+n);ty1=findfa(y+n);
        tx2=findfa(x+2*n);ty2=findfa(y+2*n);
        if(c==1)
        {
            if( tx0==ty1 || tx0==ty2 )ans++;
            else fa[tx0]=ty0,
                 fa[tx1]=ty1,
                 fa[tx2]=ty2;
        }
        else
        {
            if( tx0==ty0 || tx0==ty1 )ans++;
            else fa[tx0]=ty2,
                 fa[tx1]=ty0,
                 fa[tx2]=ty1;
        }
    }
    printf("%d\n",ans);
    return 0;
}