240. 食物链

题目链接：https://www.acwing.com/problem/content/description/242/

思路

将域扩大成3倍 x 吃 x+N,x+N吃x+2N，x+2N吃x，于是如果出现了x吃y的关系，就可以得出下面图片所示的种族关系。 同一个颜色表示同一个物种，箭头代表吃的关系。 那么就可以得出： 1.如果a和b都指向c，那么a和b就是同一类 2.如果a吃b也吃c，那么b和c是同一类

代码

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;

int N,K;
int fa[maxn];
void init(){
    for(int i = 1;i<=3*N;i++) fa[i] = i;
}
int find(int x){
    return fa[x] == x? x: fa[x] = find(fa[x]);
}
void join(int x,int y){
    fa[find(x)] = find(y);
}
int main(){
    // debug;
    ios;
    cin>>N>>K;
    init();
    int ans = 0;
    while(K--){
        int op,x,y;
        cin>>op>>x>>y;
        if(x>N || y>N) ans++;
        else if(op == 2 && x==y) ans++;
        else{
            if(op == 1){
                if(find(x) == find(y+N) || find(x) == find(y+2*N)) ans++;
                else join(x,y),join(x+N,y+N),join(x+2*N,y+2*N);
            }else{
                if(find(x) == find(y) || find(x) == find(y+N)) ans++;
                else join(x,y+2*N),join(x+2*N,y+N),join(y,x+N);
            }
        }
    }
    cout<<ans<<'\n';


    return 0;
}