poj 1182 并查集

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<string>
 4 #include<string.h>
 5 #include<map>
 6 #include<math.h>
 7 #define N 50005
 8 using namespace std;
 9 // rank[x] 表示 parent[x]与x 的关系, rank[x]=0 同类， rank[x]=1 根吃x, rank[x]=2 ， x吃根
10 int rank[N]; 
11 int parent[N];
12 int n;
13 void init()
14 {
15     for(int i=1;i<=n;i++)
16     {
17         parent[i]=i;
18         rank[i] = 0;
19     }
20 }
21 int Find(int x)
22 {
23     if(x== parent[x]) return x;
24     int temp_parent=parent[x];
25     parent[x]=Find(parent[x]);
26     rank[x]=(rank[temp_parent]+rank[x])%3;  //因为，根节点连到另一个新的根节点后，根节点有变化，故需要更新x到新节点的关系
27     return parent[x];
28 }
29 void Union(int x, int y,int D)
30 {
31      int xf=Find(x);
32      int yf=Find(y);
33      parent[xf]=yf;
34      rank[xf]=(rank[y]+D-rank[x]+3 )%3;  // 更新根节点到另一个根节点的关系
35 }
36 int main()
37 {
38     int m;
39     scanf("%d%d",&n,&m);
40 
41     int i,j,D,u,v,sum=0;
42     init();
43     for(int i=0;i<m;i++)
44     {
45         scanf("%d%d%d",&D,&u,&v);
46         if(u>n || v>n ||(D==2 && u==v)) {
47             sum++;
48             continue;
49         }
50         int uu= Find(u);
51         int vv= Find(v);
52         if(uu == vv)   //属同一子集，可以判断关系
53         {
54             if((rank[u] - rank[v] +3)%3 !=D-1)
55                 sum++;
56         }
57         else  
58         {
59 
60             Union(u,v,D-1);
61         }
62     }
63     printf("%d\n",sum);
64 
65     return 0 ;
66 }