poj 1703（带权并查集）

 1 #include<iostream>
 2 #include<cstdio>
 3 
 4 using namespace std;
 5 
 6 int parent[200005];
 7 
 8 int Getparent(int x)
 9 {
10     if(x!=parent[x])
11         parent[x] = Getparent(parent[x]);
12     return parent[x];
13 }
14 
15 void Union(int x,int y)
16 {
17     int a = Getparent(x),b = Getparent(y);
18     if(a!=b)
19         parent[b] = a;
20 }
21 
22 int main()
23 {
24     int t;
25     while(scanf("%d",&t)!=EOF)
26     {
27         while(t--)
28         {
29             int n,m;
30             scanf("%d%d",&n,&m);
31             for(int i=0;i<n+n+1;i++)
32             {
33                 parent[i] = i;
34             }
35             for(int i=0;i<m;i++)
36             {
37                 char s;
38                 int a,b;
39                 getchar();
40                 scanf("%c %d %d",&s,&a,&b);
41                 if(s==‘A‘)
42                 {
43                     if(Getparent(a) == Getparent(b)||Getparent(a+n)==Getparent(b+n))
44                         printf("In the same gang.\n");
45                     else if(Getparent(a) == Getparent(b+n)||Getparent(b) == Getparent(a+n))
46                         printf("In different gangs.\n");
47                     else
48                         printf("Not sure yet.\n");
49                 }
50                 else
51                 {
52                     Union(a,b+n);
53                     Union(a+n,b);
54                 }
55             }
56         } 
57     }
58     return 0;
59 }