$\huge \color{orange}{成仙之路->}$ $\huge \color{purple}{算法基础课题解}$

思路：

1. d[x]表示 x 到根节点的距离，若(d[x]-d[y])%3==0,则 X 和 Y 是同类，若(d[x]-d[y]-1)%3==0，则 X 吃 Y
2. 判断 X 和 Y 是同类：若 X 和 Y 在同一个集合并且 X 和 Y 不是同类则 res++，否则，就合并集合并且使 X 和 Y 是同类
3. 判断 X 吃 Y：若 X 和 Y 在同一个集合并且 X 不吃 Y 则 res++，否则，就合并集合并且使 X 吃 Y

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 50010;

int n,k;
int p[N],d[N];

//找到根节点，并且维护当前点到根节点的距离
int find(int x)
{
    if(p[x]!=x)
    {
        int u=find(p[x]);
        d[x]+=d[p[x]];
        p[x]=u;
    }
    return p[x];
}

int main()
{
    cin>>n>>k;

    for(int i=1;i<=n;i++) p[i]=i;

    int res=0;
    while(k--)
    {
        int t,a,b;
        cin>>t>>a>>b;

        if(a>n||b>n) res++;
        else 
        {
            int pa=find(a),pb=find(b);

            //X和Y是同类
            if(t==1)
            {
                //X和Y在同一个集合，但不是同类
                if(pa==pb&&(d[a]-d[b])%3) res++;

                //X和Y不在同一个集合，合并集合并使X和Y是同类
                else if(pa!=pb)
                {
                    p[pa]=pb;
                    d[pa]=d[b]-d[a];
                }
            }

            //X吃Y
            else 
            {
                //X和Y在同一个集合，但X不吃Y
                if(pa==pb&&(d[a]-d[b]-1)%3) res++;

                //X和Y不在同一个集合，合并集合并使X吃Y
                else if(pa!=pb)
                {
                    p[pa]=pb;
                    d[pa]=d[b]-d[a]+1;
                }
            }
        }
    }

    cout<<res<<endl;

    return 0;
}