poj 1703 Find them, Catch them (并查集)

 1 //Accepted    900K    329MS    C++    961B    2014-03-28 16:37:52
 2 #include<stdio.h>
 3 #define N 100000
 4 int set[2*N+1];
 5 int find(int x)
 6 {
 7     if(x!=set[x])
 8         set[x]=find(set[x]);
 9     return set[x];
10 } 
11 void merge(int a,int b)
12 {
13     int x=find(a);
14     int y=find(b);
15     if(x==y) return;
16     set[x]=y;
17     
18 }
19 int main(void)
20 {
21     int t,n,m,a,b;
22     char op;
23     scanf("%d",&t);
24     while(t--)
25     {
26         scanf("%d%d%*c",&n,&m);
27         for(int i=0;i<=n+N;i++) set[i]=i;
28         for(int i=0;i<m;i++){
29             scanf("%c%d%d%*c",&op,&a,&b);
30             if(op==‘D‘){
31                 merge(a,N+b);
32                 merge(b,N+a);
33             }else{
34                 int x=find(a);
35                 int y=find(b);
36                 if(x==y){
37                     puts("In the same gang.");
38                 }else if(x==find(b+N) || y==find(a+N)){
39                     puts("In different gangs.");
40                 }else puts("Not sure yet.");
41             } 
42         } 
43     }
44     return 0;
45 }

 1 //Accepted    900K    297MS    C++    1051B    2014-03-28 16:12:36
 2 /*
 3     种类并查集。 
 4 */
 5 #include<stdio.h>
 6 #define N 100005
 7 int set[N],rank[N];
 8 int n,m;
 9 int find(int x)
10 {
11     if(x!=set[x]){
12         int t=set[x];
13         set[x]=find(set[x]);
14         rank[x]=(rank[x]+rank[t])&1;
15     }
16     return set[x];
17 }
18 void merge(int a,int b)
19 {
20     int x=find(a);
21     int y=find(b);
22     if(x==y) return;
23     set[y]=x;
24     rank[y]=(rank[a]-rank[b]+1)&1;   
25 }
26 int main(void)
27 {
28     int t,a,b;
29     char op;
30     scanf("%d",&t);
31     while(t--)
32     {
33         scanf("%d%d%*c",&n,&m);
34         for(int i=0;i<=n;i++){
35             rank[i]=0;set[i]=i;
36         }
37         for(int i=0;i<m;i++){
38             scanf("%c%d%d%*c",&op,&a,&b);
39             if(op==‘A‘){
40                 int x=find(a);
41                 int y=find(b);
42                 if(x==y){
43                     if(rank[a]==rank[b]) puts("In the same gang.");
44                     else puts("In different gangs.");
45                 }else puts("Not sure yet.");            
46             }else{
47                 merge(a,b);
48             }
49         }
50     }
51     return 0;
52 }