POJ1182 食物链[并查集]

食物链

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 30510		Accepted: 8883

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

Sample Output

Source

Noi 01

食物链真的是一道很经典的并查集的题目，注意单例输入

code:

 1 #include <iostream>   
 2 #include <iomanip>   
 3 #include <fstream>   
 4 #include <sstream>   
 5 #include <algorithm>   
 6 #include <string>   
 7 #include <set>   
 8 #include <utility>   
 9 #include <queue>   
10 #include <stack>   
11 #include <list>   
12 #include <vector>   
13 #include <cstdio>   
14 #include <cstdlib>   
15 #include <cstring>   
16 #include <cmath>   
17 #include <ctime>   
18 #include <ctype.h> 
19 using namespace std;
20 
21 #define MAXN 50005
22 
23 int n,k;
24 int father[MAXN],rankk[MAXN];
25  
26 int Find_father(int x) /* 压缩路径，重新计算节点的 rankk */
27 {
28     int t;
29     if(father[x]==-1)
30         return x;
31     else 
32         t=Find_father(father[x]);
33     rankk[x]=(rankk[father[x]]+rankk[x])%3;
34     father[x]=t;
35     return t;
36 }
37 void Union(int x,int y,int u,int v,int w)
38 {
39     father[y]=x;
40     rankk[y]=(rankk[u]-rankk[v]+w+3)%3;
41 }
42 int main()
43 {
44     int i,j,a,b,c,x,y;
45     int ans=0;
46     scanf("%d%d",&n,&k);
47     memset(rankk,0,sizeof(rankk));
48     memset(father,-1,sizeof(father));
49     while(k--)
50     {
51         scanf("%d%d%d",&c,&a,&b);
52         if(a>n||b>n)
53         {
54             ans++;
55             continue;
56         }
57         if(c==2&&a==b)
58         {
59             ans++;
60             continue;
61         }
62         if(c==1&&a==b)
63             continue;
64         x=Find_father(a);
65         y=Find_father(b);
66         if(x==y)
67         {
68             if(c==1&&rankk[a]!=rankk[b])
69             {
70                 ans++;
71                 continue;
72             }
73             if(c==2&&((rankk[a]+1)%3!=rankk[b]||a==b))
74             {
75                 ans++;
76                 continue;
77             }
78         }
79         else 
80             Union(x,y,a,b,c-1);
81     }
82     printf("%d\n",ans);
83     return 0;
84 }