[TIOJ] 1448. 食物鏈 / [POJ] 1182. 食物链

題目連結:http://tioj.infor.org/problems/1448 / http://poj.org/problem?id=1182

---

經典的並查集應用，想法大概就跟並查集的大多數用途一樣，考慮把每個動物X分三種類型$X_A, X_B, X_C$，代表若X為A的情況或X為B的情況...，那要兩種動物$X, Y$為同一種的話合併的話，顯然就是合併$X_A \equiv Y_A, X_B \equiv Y_B, X_C \equiv Y_C$，吃的話則是$X_A \equiv Y_B, X_B \equiv Y_C, X_C \equiv Y_A$，這樣的話要判斷是否為假話的話就變容易了，仔細想想會發現不可能有一種動物$X$，他在某次操作後$X_A \equiv X_B \lor X_B \equiv X_C \lor X_C \equiv X_A$，所以只要操作前看看沒有要合併的人他的集合是不是原本就一樣就好。
p.s POJ上範圍不太一樣，這裡是TIOJ的範圍(而且動態配置貌似POJ會TLE)

#include <bits/stdc++.h>
using namespace std;
#define FAKE ans++;continue;

const int N = 500000;

class DJS{
	private:
		int *arr;
	public:
		void init(int T){
			arr=new int[T];
			for(int i=0;i<T;i++)
				arr[i]=i;
		}
		void merge(int a, int b){
			arr[query(a)]=query(b);
		}
		int query(int x){
			if(arr[x]!=x) arr[x]=query(arr[x]);
			return arr[x];
		}

} djs;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n, k;cin>>n>>k;
	int ans=0;
	djs.init(3*(n+1));
	while(k--){
		int d, x, y;cin>>d>>x>>y;
		if(x>n or y>n){FAKE}
		if(d==1){
			if(djs.query(x+n*0)==djs.query(y+n*1) or\
				djs.query(x+n*0)==djs.query(y+n*2)){
				FAKE
			}else{
				djs.merge(x+n*0, y+n*0);
				djs.merge(x+n*1, y+n*1);
				djs.merge(x+n*2, y+n*2);
			}
		}else if(d==2){
			if(x==y or \
				djs.query(x+n*0)==djs.query(y+n*0) or\
				djs.query(x+n*0)==djs.query(y+n*2)){
				FAKE
			}else{
				djs.merge(x+n*0, y+n*1);
				djs.merge(x+n*1, y+n*2);
				djs.merge(x+n*2, y+n*0);
			}

		}
	}
	cout<<ans<<'\n';
	return 0;
}