食物链（并查集）

题目：https://ac.nowcoder.com/acm/contest/22904/1024

思路：这道题网络上有很多思路，可以开三个并查集，可以使用带权并查集，但是有一个大佬的思路是这样的，将总结点的数量增加到3n个，把整个节点区域分为n，2*n，3*n三个部分，我们可以物种a的一个节点对应物种b的两个节点，如果是同类，我们就把他们通过范围对应起来（如a_n,a_2*n,a_3*n和b_n,b_2*n,b _3*n对应），如果是不是同类，我们让这个节点指向下一个范围的节点（如a_n,a_2*n,a_3*n和b_2*n,b_3*n,b _n对应)，如此一来我们只需要判断不同区域范围的节点之间的关系即可

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 55000;
int a[3*maxn];
void init(int x){
    for(int i=0;i<3*x;i++){
        a[i] = i;
    }
}
int find(int x){
    if(a[x] == x) return x;
    return a[x] = find(a[x]);
}
void join(int x,int y){
    if(find(x) != find(y)) {
        a[find(x)] = find(y);
    }
}
int main(){
    int n,k;
    scanf("%d %d",&n,&k);
    init(n);
    int ans =0;
    while(k--){
        int d,x,y;
        scanf("%d %d %d",&d,&x,&y);
        if((x<1 || x>n || y<1 || y > n) || (d==2 && x==y)) {
            ans++;
            continue;
        }
        if(d==1) {
            if(find(x)==find(y+n) || find(x+n)==find(y)) ans++;
            else {
                join(x,y);
                join(x+n,y+n);
                join(x+2*n,y+2*n);
            }
        }
        else if(d==2){
            if(find(x)==find(y) || find(x+n)==find(y)) ans++;
            else {
                join(x,y+n);
                join(x+n,y+2*n);
                join(x+2*n,y);
            }
        }
    }
    printf("%d",ans);
    return 0;
}