Find them, Catch them(POJ 1703 关系并查集)

 1 #include <stdio.h>
 2 #include <string.h>
 3 const int maxn = 100005;
 4 
 5 int n,m;
 6 int p[maxn];//保存父节点
 7 int r[maxn];//保存与父节点的关系，0为同类。1为不同类
 8 
 9 void make_set()
10 {
11     for(int i = 1; i <= n; i++)
12     {
13         p[i] = i;
14         r[i] = 0;
15     }
16 }
17 
18 int find(int x)
19 {
20     if(x == p[x])
21         return x;
22     int tmp = p[x];            //记录父亲节点，方便更新r[].
23     p[x] = find(p[x]);
24     r[x] = (r[x]+r[tmp])%2;        //根据子节点与父亲节点的关系和父节点与爷爷节点的关系，推导子节点与爷爷节点的关系  
25     return p[x];
26 }
27 
28 void merge(int a, int b)
29 {
30     int fa = find(a);
31     int fb = find(b);
32     p[fa] = fb;
33     r[fa] = (r[a]+r[b]+1)%2;        //fx与x关系 + x与y的关系 + y与fy的关系 = fx与fy的关系 
34 }
35 
36 int main()
37 {
38     int test,a,b;
39     char str[2];
40     freopen("in.txt","r",stdin);
41     scanf("%d",&test);
42     while(test--)
43     {
44         scanf("%d %d",&n,&m);
45         make_set();
46         while(m--)
47         {
48             scanf("%s %d %d",str,&a,&b);
49 
50             if(str[0] == ‘A‘)
51             {
52                 if(find(a) != find(b))        //如果根节点不同，则不能判断关系  
53                 {
54                     printf("Not sure yet.\n");
55                     continue;
56                 }
57                 else
58                 {
59                     if(r[a] == r[b])
60                         printf("In the same gang.\n");
61                     else printf("In different gangs.\n");
62                 }
63             }
64             else
65             {
66                 merge(a,b);
67             }
68         }
69     }
70     return 0;
71 }