题目链接

食物链

题目思路：带权并查集

设0为a,b同级 a1b为a吃b a2b为b吃a
第一次写带权并查集，希望在最近的刷题中能有所提高

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int Max=1e6;
int n,k;
int ft[Max],d[Max];
void init()
{
    for(int i=1;i<=n;i++)
        ft[i]=i;
}
int find(int x)
{
    if(ft[x]==x) return x;
    else
    {
        int t=find(ft[x]);
        d[x]+=d[ft[x]];
        ft[x]=t;
    }
    return ft[x];
}
int main()
{
    cin>>n>>k;
    init();
    int sum=0;
    while(k--)
    {
        int c,a,b;
        cin>>c>>a>>b;
        if(a>n||b>n)
        {
            sum++;
            continue;
        }
        else
        {
            int fa=find(a),fb=find(b);
            if(c==1)
            {
                if(fa==fb&&(d[b]-d[a])%3!=0)
                    sum++;
                else if(fa!=fb)
                {
                    ft[fa]=fb;
                    d[fa]=d[b]-d[a];
                }
            }
            else if(c==2)
            {
                if(fa==fb&&(d[a]-d[b]+1)%3!=0)
                    sum++;
                else if(fa!=fb)
                {
                    ft[fa]=fb;
                    d[fa]=d[b]-d[a]+2;
                }
            }
        }
    }
    cout<<sum<<endl;
    return 0;
}