Codevs 1074[NOI 2002]食物連鎖

ACチャネル:http://codevs.cn/problem/1074/
[解析]
このような判断が矛盾しているかどうかを見ると、考えて調べます.
AがBを食べ、BがCを食べると、CがAを食べるという結論が出るので、私たちが使っているアルゴリズムはこの結論に配慮する必要があります.
この操作は表示しにくいので、いくつかの虚点を設けて補助します.(AとBは同じ集合で(A,B)と表す)
私たちは(A',B)をAがBを食べることを表します.(A’,B’)と(A,B’)もAがBを食べることを表す.(A,B)はそれらが同類であることを示す.
AがBを食べ、BがCを食べると、(A’,B)かつ(A’,B’);
BはCを食べるので、(B',C).
(B',C)そして(A',B')から(A',B',C)を得ることができて、だから(A',C)、およびCはAを食べます.
したがって,我々の定義によれば,AがB,BがCを食べると,CがAを食べることができ,上記の結論と一致する.具体的な実装方法はコードを参照してください.

#include <iostream>
#include <cstdio>

using namespace std;

int n,k,tot;
int fa[150010];

inline int find(int x){
	int tmp=x,pre;
	while(tmp!=fa[tmp])tmp=fa[tmp];
	while(x!=tmp){
		pre=fa[x];
		fa[x]=tmp;
		x=pre;
	}
	return tmp;
}

inline void merge(int x,int y){
	int fx=find(x),fy=find(y);
	fa[fx]=fy;
}

int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=3*n;i++)fa[i]=i;
	for(int i=1;i<=k;i++){
		int d,x,y;
		scanf("%d%d%d",&d,&x,&y);
		if(x>n||y>n){tot++;continue;}
		if(d==2&&x==y){tot++;continue;}
		if(d==1&&(find(x+1*n)==find(y)||find(x+2*n)==find(y)||find(x)==find(y+1*n)||
find(x)==find(y+2*n)||find(x+1*n)==find(y+2*n)||find(x+2*n)==find(y+1*n))){
			tot++;continue;
		}
		if(d==2&&(find(x)==find(y)||find(x+1*n)==find(y+2*n)||find(x+2*n)==find(y)||
find(x)==find(y+1*n)||find(x+1*n)==find(y+1*n)||find(x+2*n)==find(y+2*n))){
			tot++;continue;
		}
		if(d==1){
			merge(x,y);
			merge(x+1*n,y+1*n);
			merge(x+2*n,y+2*n);
		}
		if(d==2){
			merge(x+1*n,y);
			merge(x+2*n,y+1*n);
			merge(x,y+2*n);
		}
	}
	printf("%d
",tot);
	return 0;
}