POJ1703Find them, Catch them

Find them, Catch them

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 37722		Accepted: 11632

Description

The police office in Tadu City decides to say ends to the chaos, as launch actions to root up the TWO gangs in the city, Gang Dragon and Gang Snake. However, the police first needs to identify which gang a criminal belongs to. The present question is, given two criminals; do they belong to a same clan? You must give your judgment based on incomplete information. (Since the gangsters are always acting secretly.)

Assume N (N <= 10^5) criminals are currently in Tadu City, numbered from 1 to N. And of course, at least one of them belongs to Gang Dragon, and the same for Gang Snake. You will be given M (M <= 10^5) messages in sequence, which are in the following two kinds:

1. D [a] [b]
where [a] and [b] are the numbers of two criminals, and they belong to different gangs.

2. A [a] [b]
where [a] and [b] are the numbers of two criminals. This requires you to decide whether a and b belong to a same gang.

Input

The first line of the input contains a single integer T (1 <= T <= 20), the number of test cases. Then T cases follow. Each test case begins with a line with two integers N and M, followed by M lines each containing one message as described above.

Output

For each message "A [a] [b]" in each case, your program should give the judgment based on the information got before. The answers might be one of "In the same gang.", "In different gangs." and "Not sure yet."

Sample Input

Sample Output

Not sure yet.
In different gangs.
In the same gang.

又把种类并查集复习了一遍发现以前写的好乱。
做这种题就是要设一种关系用来表示它与父节点的关系，用a[x]来表示x与x父节点的关系，a[x] == 0表示x与父节点同类，否则异类
那么x的父节点与x的关系是跟x与他父节点的关系是一样的，这点比食物链那题简单
而求子节点与爷爷节点关系公式 （a[father[x] + a[x] ) % 2;通过枚举可以得到。因此在find_fahter更改关系时提供了凭据

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <cstdio>
 5 using namespace std;
 6 const int MAX = 100000 + 10;
 7 int father[MAX],a[MAX];
 8 int find_father(int x)
 9 {
10     if(x == father[x])
11         return x;
12     int t = find_father(father[x]);
13     a[x] = (a[father[x]] + a[x]) % 2;
14     return father[x] = t;
15 }
16 void Union(int x,int y)
17 {
18     int fx = find_father(x);
19     int fy = find_father(y);
20     father[fx] = fy;
21     if(a[y] == 0)  //x和y是不同帮派， 如果y和fy是相同的帮派，｛如果x和fx是同一帮派的话，fx就与fy不同，a[fx] = 1 - 0;如果x和fx不是同一帮派 fx和fy相同，a[fx] = 1 - 1；如果y和fy是不同的帮派即a[y] == 1,那么x和fy肯定是一派的，
22     {
23         a[fx] = 1 - a[x];
24     }
25     else
26     {
27         a[fx] = a[x];
28     }
29 }
30 int main()
31 {
32     int t,n,m;
33     scanf("%d", &t);
34     while(t--)
35     {
36         scanf("%d%d", &n,&m);
37         for(int i = 0; i <= n; i++)
38         {
39             father[i] = i;
40             a[i] = 0;
41         }
42         char ch;
43         int x,y;
44         getchar();
45         while(m--)
46         {
47             scanf("%c%d%d", &ch,&x,&y);
48             getchar();
49             if(ch == 'A')
50             {
51                 int fx = find_father(x);
52                 int fy = find_father(y);
53                 if(fx != fy)
54                 {
55                     printf("Not sure yet.
");
56                 }
57                 else
58                 {
59                     if(a[x] == a[y])
60                     {
61                         printf("In the same gang.
");
62                     }
63                     else
64                         printf("In different gangs.
");
65                 }
66 
67             }
68             else if(ch == 'D')
69             {
70                 Union(x,y);
71             }
72         }
73     }
74 
75     return 0;
76 }

View Code

之前结构体做的比较麻烦，原理一样的

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <algorithm>
 5 using namespace std;
 6 const int MAX = 100000+10;
 7 struct person
 8 {
 9     int num;
10     int bang;
11     int father;
12 };
13 person per[MAX];
14 int find_father(person &node)
15 {
16     if(node.father == node.num)
17         return node.father;
18     int temp = node.father;   //这个很重要，因为是通过当前数与父节点关系，父节点与总父节点的关系来判断当前数与总父节点的关系，
19     node.father = find_father(per[temp]);
20     node.bang = (node.bang + per[temp) % 2; //本来这里写的是（node.bang + per[node.father)）%2; 因为经过上一步递归更新父节点，此时的node.father已经是总父节点了，so...
21     return node.father;
22 }
23 int main()
24 {
25     int t;
26     scanf("%d", &t);
27     while(t--)
28     {
29         int n,m,a,b,fa,fb;
30         char c;
31         scanf("%d%d", &n,&m);
32         getchar();
33         for(int i = 0; i <= n; i++)
34         {
35             per[i].num = i;
36             per[i].father = i;
37             per[i].bang = 0;
38         }
39         while(m--)
40         {
41             scanf("%c%d%d", &c,&a,&b);
42             getchar();
43 
44             if(c == 'D')
45             {
46                 fa = find_father(per[a]);
47                 fb = find_father(per[b]);
48                 if(fa != fb) {
49                     per[fb].father = fa;
50                     if(per[a].bang== 0)    //这里要举例找规律
51                         per[fb].bang = 1 - per[b].bang;
52                     else
53                         per[fb].bang = per[b].bang;
54                 }
55             }
56             else if(c == 'A')
57             {
58                 fa = find_father(per[a]);
59                 fb = find_father(per[b]);
60                 if(fa != fb)
61                     printf("Not sure yet.
");
62                 else
63                 {
64                     if(per[a].bang == per[b].bang)
65                         printf("In the same gang.
");
66                     else
67                         printf("In different gangs.
");
68                 }
69             }
70 
71         }
72     }
73     return 0;
74 }

View Code