食物鏈 Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 32266 Accepted: 9405 Description 動物王國中有三類動物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），輸出假話的總數。 Input 第一行是兩個整數N和K，以一個空格分隔。 以下K行每行是三個正整數 D，X，Y，兩數之間用一個空格隔開，其中D表示說法的種類。 若D=1，則表示X和Y是同類。 若D=2，則表示X吃Y。 Output 只有一個整數，表示假話的數目。 Sample Input 100 7 1 101 1 2 1 2 2 2 3 2 3 3 1 1 3 2 3 1 1 5 5 Sample Output 3 Source Noi 01 自己寫了200多行的代碼，結果發現確實wa，在網上百了一下，發現這題六七十代碼就能過了，哎，這題看的解題報告，並查集中的經典啊，推薦大家看： http://blog.csdn.net/c0de4fun/article/details/7318642 [cpp] #include <iostream> #include <stdio.h> #include <cstring> using namespace std; int a[50010]; int val[50010]; int main() { int findparent(int x); void crlcle(int a,int b,int x,int y,int d); int i,j,n,m,s,t,res; int d,x,y,parent_x,parent_y; scanf("%d %d",&n,&m); memset(val,0,sizeof(val)); for(i=1;i<=n;i++) { a[i]=i; } res=0; for(i=1;i<=m;i++) { scanf("%d %d %d",&d,&x,&y); if((x>n||y>n)||(d==2&&x==y)) { res++; continue; } parent_x=findparent(x); parent_y=findparent(y); if(parent_x!=parent_y) { crlcle(parent_x,parent_y,x,y,d); }else { if(d==1) { if(val[x]!=val[y]) { res++; } }else { if((3-val[x]+val[y])%3!=1) { res++; } } } } printf("%d\n",res); return 0; } int findparent(int x) { int k1,k2,s,t; k1=x; s=0; while(x!=a[x]) { s+=val[x]; x=a[x]; } while(k1!=a[k1]) { t=s%3; s-=val[k1]; val[k1]=t; k2=a[k1]; a[k1]=x; k1=k2; } return x; } void crlcle(int c,int b,int x,int y,int d) { int i,j; a[b]=c; val[b]=(3-val[y]+(d-1)+val[x])%3; }
