题解：SP1442 CHAIN - Strange Food Chain

双倍经验：P2024 [NOI2001] 食物链

思路：

一眼鉴定为并查集。

观察题目发现有三种状态，考虑使用种类并查集（又称扩展域并查集）。

既然有三种状态那么种类并查集自然也要开三倍。

CODE:

#include<bits/stdc++.h>
using namespace std;
int fa[150010];
int Get_Find(int x){//寻找父节点
    if(x==fa[x]) return x;
    return fa[x]=Get_Find(fa[x]);//路径压缩
}
void Merge(int x,int y){//合并（乱认祖先）
    x=Get_Find(x),y=Get_Find(y);
    if(x==y) return;
    fa[x]=y;
}
main(){
    int t;
    cin>>t;
    while(t--){
        int x,y,z;
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=150001;i++) fa[i]=i;//初始化
        int cnt=0;
        for(int i=1;i<=m;i++){
        	int x,y,op;
        	cin>>op>>x>>y;
        	if(x>n||y>n){
        	    cnt++;
        	    continue;
        	}
        	if(op==1){
        		if(Get_Find(x+n)==Get_Find(y)||Get_Find(x+2*n)==Get_Find(y)){//判断是否不合法
        			cnt++;
        			continue;
    			}
    			Merge(x,y);//合并
    			Merge(x+n,y+n);
    			Merge(x+2*n,y+2*n);
    		}else{
    			if(Get_Find(x+2*n)==Get_Find(y)||Get_Find(x)==Get_Find(y)){
        			cnt++;
        			continue;
    			}
    			Merge(x,y+2*n);
    			Merge(x+n,y);
    			Merge(x+2*n,y+n);
    		}
    	}
    	cout<<cnt<<"\n";
    }
}