pku 1182(种类并查集)

解题思路来自discuss:http://poj.org/showmessage?message_id=152847
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 #define MAXN 50050
 6 int parent[MAXN];
 7 int kind[MAXN];
 8 int n,m,tag;
 9 
10 void Initiate()
11 {
12     for(int i=0;i<=n;i++){
13         parent[i]=i;
14     }
15     memset(kind,0,(n+2)*sizeof(kind[0]));
16 }
17 
18 int Find(int x)
19 {
20     if(x==parent[x]){
21         return parent[x];
22     }
23     int tmp=Find(parent[x]);
24     kind[x]=(kind[x]+kind[parent[x]])%3;
25     return parent[x]=tmp;
26 }
27 
28 void Union(int a,int b)
29 {
30     int r1=Find(a),r2=Find(b);
31     parent[r1]=r2;
32     kind[r1]=(kind[b]-kind[a]+3+tag-1)%3;
33 }
34 
35 
36 int main()
37 {
38   //  freopen("1.txt","r",stdin);
39     int a,b,ans=0;
40     scanf("%d%d",&n,&m);
41     Initiate();
42     while(m--){
43         scanf("%d%d%d",&tag,&a,&b);
44         if(a>n||b>n||(tag==2&&a==b)){ ans++;continue; }
45         if(Find(a)!=Find(b)){
46             Union(a,b);
47         }else {
48             if((kind[a]-kind[b]+3)%3!=(tag-1))
49                 ans++;
50         }
51     }
52     printf("%d
",ans);
53     return 0;
54 }
View Code