食物連鎖の問題解

タイトルの説明
動物王国には3種類の動物A,B,Cがあり,この3種類の動物の食物連鎖は興味深い環状を構成している.AはBを食べ、BはCを食べ、CはAを食べる.
既存のN個の動物は、1−Nで番号付けされている.どの動物もA,B,Cの一種ですが、どれなのか分かりません.
このN個の動物が構成する食物連鎖関係を2つの説で説明する人がいる.

第1の言い方は1 X Yであり、XとYが同類であることを示す.

第2の言い方は2 X Yで、XがYを食べることを表しています.

この人はN個の動物に対して、上記の2つの言い方を使って、次から次へとK文の言葉を言って、このK文の言葉はあるのは本当で、あるのは偽物です.一言が次の3つの1つを満たすと、この言葉はうそで、そうでなければ本当のことです.

現在の話は前のいくつかの本当の話と衝突し、うそ

である.

現在の話の中でXあるいはYはNより大きくて、うそ

です.

現在の言葉はXがXを食べることを表して、うその

です
あなたの任務は、与えられたN文とK文に基づいて、偽話の総数を出力することです.
入力フォーマット
1行目の2つの整数、N、Kは、N個の動物がいることを示し、K文は.
2行目から行ごとに一言(テーマの要求に従って、サンプルを参照)
出力フォーマット
1行、整数で、うその総数を表します.
サンプル入力

100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5

サンプル出力

3

ぶんせき
この問題は、みな見ているはずだ.しかし、私たちは3倍のメンテナンスとコレクションを調べる必要があります......うん?また玄学になった.
まず,3つの生物群系A,B,C(すなわち,3つの並列集合)を定義する.Aは中立者、Bは生産者、Cは消費者を定義することができます.この時関係は明らかである:AはBを食べ、AはCに食べられる.Bを中立者と定義することもでき、Cが生産者になり、Aが消費者を表す.このとき関係:BはCを食べ、BはAに食べられる.もちろんいいです.この时、CはAを食べ、CはBに食べられます.
だから、同じ群系の2つの生物が同じ集合に属している場合は、彼らが同類であることを意味します.もし异なる群系の中の2つの生物が同じ集合に属するならば、A群系の中の生物はきっとB群系の中のを食べることができて、B群系の中のC群系の中のを食べて、C群系はB群系の中のを食べます
これにより,同じ集合に属するが意味の異なる生物の相互関係が区別される.
そして、実現は簡単ですね.
ACコード

#include 

const int MAXN = 150005;
//        
int fa[MAXN];

//      
// 1~n  A  ，n+1~2*n  B  ，n*2+1~n*3  C  
void Make_Set(int n) {
	for(int i = 0; i <= 3 * n; i++) fa[i] = i;
}

int Find_Set(int s) {
	if(fa[s] != s) return fa[s] = Find_Set(fa[s]);
	else return fa[s];
}

void Union_Set(int s, int e) { 
	int u = Find_Set(s);
	int v = Find_Set(e);
	if(u == v) return ;
	fa[v] = u;
}

int main() {
	int n, k;
	//  n   ，k  
	scanf ("%d %d", &n, &k);
	Make_Set(n);
	int ans = 0;
	for(int i = 1; i <= k; i++) {
		int t, x, y;
		scanf ("%d %d %d", &t, &x, &y);
        if(x > n || y > n) { //   x，y      ？
			ans++; //     
			continue;
		}
        if(t == 2 && x == y) { //        ？
			ans++; //     
			continue;
		}
		if(t == 1) {
			if(Find_Set(y) == Find_Set(x + 2 * n) 
			|| Find_Set(x) == Find_Set(y + 2 * n)) { 
			//      A    y    C    x？
			//      A    x    C    y？
			//          ，       
				ans++; //     
				continue;
			}            
			Union_Set(x, y); 
			Union_Set(x + n, y + n);            
			Union_Set(x + 2 * n, y + 2 * n);
			//        x，y      
		}
        else {            
			if(Find_Set(x) == Find_Set(y) 
			|| Find_Set(x) == Find_Set(y + 2 * n)) {
			//   x，y  ？
			//      C    y    A    x？
			//   
				ans++; //     
				continue;
			}            
			Union_Set(x + 2 * n, y); // C   A            
			Union_Set(x + n, y + 2 * n); // B   C          
			Union_Set(x, y + n); // A   B          
		}  
	}
	printf("%d
", ans); 
	return 0;
}