雙倍經(jīng)驗(yàn)：P2024 [NOI2001] 食物鏈

思路：

一眼鑒定為并查集。

觀察題目發(fā)現(xiàn)有三種狀態(tài)，考慮使用種類并查集（又稱擴(kuò)展域并查集）。

既然有三種狀態(tài)那么種類并查集自然也要開(kāi)三倍。

CODE:

#include<bits/stdc++.h>
using namespace std;
int fa[150010];
int Get_Find(int x){//尋找父節(jié)點(diǎn)
    if(x==fa[x]) return x;
    return fa[x]=Get_Find(fa[x]);//路徑壓縮
}
void Merge(int x,int y){//合并（亂認(rèn)祖先）
    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";
    }
}