そしてセットを調べる(基本コード+poj 1182食物連鎖)

------------------------------------------------------------------------------------------------------------
検索セット:
クエリー要素aと要素bが同じグループに属しているかどうかについてよく使用されます.
要素aと要素bが存在するグループを結合する
基本コード:【チャレンジプログラムより抜粋】

int par[MAX_X];		//  
int rank[MAX_X]; 	//    

//    
void init(int n){
	for(int i=0;i<n;i++){
		par[i]=i;
		rank[i]=0; 
	} 
} 

//     
int find(int x){
	if(par[x]==x){
		return x;
	}
	else{
		return par[x]=find(par[x]);
	}
} 

//  x y     
void unite(int x,int y){
	x=find(x);
	y=find(y);
	if(x==y) return;
	
	if(rank[x]<rank[y]){
		par[x]=y;
	}else{
		par[y]=x;
		if(rank[x]==rank[y]) rank[x]++;
	}
	
} 

//           
bool same(int x,int y){
	return find(x)==find(y);
} 

POJ 1182食物連鎖
本の中で紹介する主な解決方法は:
(i-Aはiが種類Aに属することを示す)
各チームに対してA,B,Cクラスに属する3つの要素を作成する.以下の符号Nは隔てている
種類1:xとyは同じクラスに属し,それぞれx-A,y-Aを合併する    x-B,y-B         x-C,y-C,
種類2:x食y・・・・それぞれx-A,y-Bを合併    x-B,y-C         x-C,y-A,
注意合併する前に矛盾を満たすかどうかを判断しなければならない.
【種類1 x-Aとy-Bまたはx-Aとy-Cが同じグループに属しているかどうかを検査する】
【種類2 x-Aとy-Aまたはx-Aとy-Cが同じグループかどうかをチェックする】

#include <cstdio>
#define MAXN 50001

int par[3*MAXN],rank[3*MAXN];

//       

//-----------------         
int main(){
	int n,k,tot=0;
	int type,x,X,y,Y;
	scanf("%d%d",&n,&k);	
	init(3*n);
	for(int i=0;i<k;i++){
		scanf("%d%d%d",&type,&X,&Y);
		x=X-1,y=Y-1;
		
		if(x<0||x>=n||y<0||y>=n){
			tot++;
			continue;
		}
		
		if(type==1){
			if(same(x,y+n)||same(x,y+2*n)){
				tot++;
			}
			else{
				unite(x,y);
				unite(x+n,y+n); 
				unite(x+2*n,y+2*n);				
			}
		}
		else{
			if(same(x,y)||same(x,y+2*n)){
				tot++;
			}else{
				unite(x,y+n);
				unite(x+n,y+2*n);
				unite(x+2*n,y);				
			}
		}
	}
		printf("%d
",tot);	
	
	return 0;
}