題目描述

動物王國中有三類動物A,B,C，這三類動物的食物鏈構成了有趣的環形。A吃B， B吃C，C吃A。

現有N個動物，以1－N編號。每個動物都是A,B,C中的一種，但是我們并不知道它到底是哪一種。

有人用兩種說法對這N個動物所構成的食物鏈關系進行描述：

第一種說法是“1 X Y”，表示X和Y是同類。

第二種說法是“2 X Y”，表示X吃Y。

此人對N個動物，用上述兩種說法，一句接一句地說出K句話，這K句話有的是真的，有的是假的。

當一句話滿足下列三條之一時，這句話就是假話，否則就是真話。

1.當前的話與前面的某些真的話沖突，就是假話；

2.當前的話中X或Y比N大，就是假話；

3.當前的話表示X吃X，就是假話。

你的任務是根據給定的N（1≤N≤50,000）和K句話（0≤K≤100,000），輸出假話的總數。

輸入

第一行是兩個整數N和K，以一個空格分隔。

以下K行每行是三個正整數 D，X，Y，兩數之間用一個空格隔開，其中D表示說法的種類。 若D=1，則表示X和Y是同類。 若D=2，則表示X吃Y。

輸出

只有一個整數，表示假話的數目

樣例輸入

Copy (如果復制到控制臺無換行，可以先粘貼到文本編輯器，再復制)

100 7 1 101 1  2 1 2  2 2 3  2 3 3  1 1 3  2 3 1  1 5 5  
樣例輸出
3
提示
    這道題半年前就做過，但是——沒做出來……（尷尬）    了解思路后發現即使是這種猥瑣的題目也還是不算難（至少比奇偶性簡單，怪我咯？），所以讓我們理理思路吧！    這道題唯一讓人欣慰的地方是只有三種動物……我們可以發現，這些動物之間的關系很巧妙，如果我們將動物之間的關系表示為有向帶權邊，就會有神奇的事發生。如果A->B的邊權值為0，那么他們就是同類；如果A->的權值為1，那么A吃B，也可理解為B被A吃。我們可以將權值為1的邊進行反轉，擴展出一種新邊，權值為-1，表示被吃關系。這樣一來，兩個動物之間的距離之和如果是3的倍數，那么他們是同類；如果A->B的距離和除以3余1，那么A就可以吃掉B；如果A->B的距離除以3余2，那么A就會被B吃。我們將所有有關系的動物放入一個并查集中，每次添加指令，如果兩個動物集合不同，就直接合并，并設置權值，否則就判斷是否合法。    至此，這道題的思路就解決了，只需要處理一些細節即可解決這道題了，那么就是代碼了（在我的代碼中，權值為1的邊是父親可以吃掉兒子，而判斷時是由兒子向上找的，所以判斷出來的值是兒子與父親的關系，所以要為2才是兒子能吃掉父親）：
#include<cstdio>int yes(int a){return (a%3+3)%3;}int OK(int x) {return x==1?0:2;}int f[50005];int dis[50005];int n,k,o;int ds(int x){	if(f[x]==0)		return 0;	return dis[x]+ds(f[x]);}int find(int x){	if(f[x]==0)		return x;	else	{		dis[x]=ds(x);		f[x]=find(f[x]);		return f[x];	}}int main(){	scanf("%d%d",&n,&k);	for(int i=1;i<=k;i++)	{		int a,b,x;		scanf("%d%d%d",&x,&a,&b);		if(a>n||b>n||(x==2&&a==b)){o++;continue;}		if(x==1&&a==b)continue;		int p=find(a),q=find(b);		if(p==q)		{			if(yes(ds(a)-ds(b))!=OK(x))				o++;		}		else		{			dis[q]=yes(ds(a)-ds(b)+x-1);			f[q]=p;		}	}	PRintf("%d",o);}