食物鏈
Time Limit: 1000MS
Memory Limit: 10000K
Total Submissions: 41134
Accepted: 11965
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
解題思路：
有三種動物，A吃B，B吃C，C吃A，有N只動物，編號1到N，用3*N個元素建立並查集，前n個元素和中間n個元素的關系是，前面的吃後面的，中間n個元素和最後n個元素的關系是中間的吃最後的，理所當然最後的n個元素與最前面n個元素的關系是，最後的吃最前面的，這樣就建立了關系的並查集。對於輸入 1 x y ，如果x 和y+n 或 x+n 和y+2n在一個集合，則為假話，否則，把他們放在同一個集合裡，unite(x,y), unite(x+n,y+n) unite(x+2n,y+2n) 。
代碼：
#include
#include
#include
using namespace std;
const int N=50002;
int k,n;
int parent[N*3];
void init(int n)
{
for(int i=1;i<=n;i++)
parent[i]=i;
}
int find(int x)
{
return parent[x]==x?x:find(parent[x]);
}
void unite(int x,int y)
{
x=find(x);
y=find(y);
if(x==y)
return;
parent[x]=y;
}
bool same(int x,int y)
{
return find(x)==find(y);
}
int main()
{
scanf("%d%d",&n,&k);
init(n*3);
int d,x,y;
int lie=0;
for(int i=1;i<=k;i++)
{
scanf("%d%d%d",&d,&x,&y);
if(x>n||y>n||x<1||y<1||(d==2&&x==y))//不合法的輸入
{
lie++;
continue;
}
int t=d;
if(t==1)
{
if(same(x,y+n)||same(x,y+2*n))//不在一個種類裡面
lie++;
else
{
unite(x,y);//合並為同一種類，3種
unite(x+n,y+n);
unite(x+2*n,y+2*n);
}
}
else
{
if(same(x,y)||same(x,y+2*n))//如果x和y同一種類或y吃x
lie++;
else
{
unite(x,y+n);//三種情況為x吃y
unite(x+n,y+2*n);
unite(x+2*n,y);
}
}
}
cout<
