#题解##P2024 [NOI2001] 食物链#

带权重的并查集（权重0代表与父节点同类，1为父节点食物即被父节点吃，2为吃父节点）

#include<bits/stdc++.h>
using namespace std;
int arr[50010],da[50010];//并查集数组和权重数组
int fi(int x)
{
    if(arr[x]!=x)
    {
        int temp=arr[x];
        arr[x]=fi(arr[x]);
        da[x]=(da[temp]+da[x])%3;//路径压缩
        return arr[x];
    }
    return x;
}
int main()
{
    int n,k,op,x,y,ans=0;
    cin>>n>>k;
    for(int i=1;i<=n;i++) arr[i]=i;
    for(int i=0;i<k;i++)
    {
        scanf("%d%d%d",&op,&x,&y);
        if(op==2&&x==y) ans++;
        else if(x>n||y>n) ans++;
        else
        {
            int a=fi(x);
            int b=fi(y);
            if(op==1)
            {
                if(a!=b)
                {
                    arr[b]=a;
                    da[b]= (3-da[y]+da[x])%3;
                }
                else if(a==b&&da[x]!=da[y]) ans++;
            }
            else
            {
                if(a!=b)
                {
                    arr[b]=a;
                    da[b]= (3-da[y]+da[x]+1)%3;
                }
                else if(a==b&&(da[y]-da[x]+3)%3!=1) ans++;
            }
        }
    }
    cout<<ans<<endl;
}