poj 1703 Find them, Catch them（并查集）

题意：一个地方有两个帮派，每个罪犯只属于其中一个帮派，D 后输入的是两个人属于不同的帮派，

A后询问两个人是否属于同一个帮派。

用op[]数组记录不跟自己在一个帮派中的一个人，然后再输入不跟自己在一个帮派的人的时候，把

这个人跟 op[]数组记录里的那个人联系起来，这两个人属于一个帮派。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <algorithm>
 6 using namespace std;
 7 const int maxn = 100010;
 8 int bin[maxn], op[maxn], n;
 9 void init()
10 {
11     for(int i = 1; i <= n; i++)
12     {
13         bin[i] = i;
14         op[i] = 0;
15     }
16 }
17 int find(int x)
18 {
19     int r, i, j;
20     r =  x;
21     while(r != bin[r])
22     r = bin[r];
23     i = x;
24     while(bin[i] != r)
25     {
26         j = bin[i];
27         bin[i] = r;
28         i = j;
29     }
30     return r;
31 }
32 /*
33 int find(int x)  //递归 路径压缩写法
34 {
35     return bin[x]==x?x:(bin[x]=find(bin[x]));
36 }
37 */
38 void merge(int x, int y)
39 {
40     int fx, fy;
41     fx = find(x);
42     fy = find(y);
43     if(fx != fy)
44     bin[fx] = fy;
45 }
46 int main()
47 {
48     int t, m, a, b;
49     char ch;
50     scanf("%d", &t);
51     while(t--)
52     {
53         scanf("%d%d", &n, &m);
54         init();
55 
56         while(m--)
57         {
58            getchar();
59            scanf("%c%d%d",&ch, &a, &b);
60            if(ch == 'A')
61            {
62                int x, y;
63                x = find(a);
64                y = find(b);
65                if(x == y)
66                printf("In the same gang.
");
67                else if(op[a]!=0&&find(op[a])==y || op[b]!=0&&find(op[b])==x)
68                printf("In different gangs.
");
69                else
70                printf("Not sure yet.
");
71            }
72            else
73            {
74                if(op[a] == 0)
75                op[a] = b;
76                else
77                merge(op[a],b);
78                if(op[b] == 0)
79                op[b] =a;
80                else
81                merge(op[b],a);
82            }
83         }
84     }
85     return 0;
86 }

poj 1703 Find them, Catch them（并查集）

相关推荐