食物链——并查集

我认为这题很好的揭示了并查集的一个本质，即将任何有关联的元素整合到一个集合里。 首先是一个常规解法，思路是通过边的权值来维护两者间的关系。

这题对于并查集的的考察并没有很常规，我们还可以用另一个思路，把情况拆分一下 ，更加简洁

#include<bits/stdc++.h>
using namespace std;
int fa[201000],n,k;
int find(int a){
     if(fa[a]==a) return a;
    else return fa[a]=find(fa[a]);
}
void merge(int a, int b){
   fa[find(a)]=find(fa[b]);
}
int main(){
    cin>>n>>k;
    for(int i=1; i<=3*n; i++)
        fa[i]=i;//初始化，每个儿子的父亲是自己
    int cnt=0;
    int v,x,y;
    for(int i=1; i<=k; i++)
    {
        cin>>v>>x>>y;
        if(x>n||y>n)
        {cnt++; continue;}
        else{
            if(v==1){
                if(find(x)==find(y+n)||find(x)==find(y+2*n))
                cnt++;
                else{
                    merge(x,y);
                    merge(x+n,y+n);
                    merge(x+2*n,y+2*n);
                }
            }
            else {
                 if(find(x)==find(y)||find(x)==find(y+2*n))
                cnt++;
                else{
                    merge(x,y+n);
                    merge(x+n,y+2*n);
                    merge(x+2*n,y);  }
                  }
        }
    }
    cout<<cnt;
    return 0;
}