POJ_2492 A Bug's Life 【并查集】

一、题面

POJ2492

二、分析

并查集判断类别的题目感觉套路都差不多。

还是先判断在不在一个集合里，在一个集合里才能判断是否同类。

若不在一个集合里则需要将这两个点联系起来。

关于联系起来后关系的变化，画几个图后发现还是异或。

为什么用0表示同类，1表示异类？画几个图发现这样表示关系变换最简单。

三、AC代码

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <fstream>
 5 
 6 using namespace std;
 7 
 8 const int MAXN = 2e3+5;
 9 int Par[MAXN];
10 bool Rank[MAXN];
11 
12 void Init()
13 {
14     memset(Par, -1, sizeof(Par));
15     memset(Rank, 0, sizeof(Rank));
16 }
17 
18 int Find(int x)
19 {
20     if(Par[x] == -1)
21         return x;
22     int t = Par[x];
23     Par[x] = Find(Par[x]);
24     Rank[x] = Rank[t]^Rank[x]; 
25     return Par[x];
26 }
27 
28 int main()
29 {
30     //freopen("input.txt", "r", stdin);
31     int T, N, M;
32     scanf("%d", &T);
33     for(int Cnt = 1; Cnt <= T; Cnt++)
34     {
35         if(Cnt!=1)
36             printf("
");
37         Init();
38         int x, y, fx, fy;
39         bool ans = true;
40         scanf("%d %d", &N, &M);
41         for(int i = 0; i < M; i++)
42         {
43             scanf("%d %d", &x, &y);
44             if(ans)
45             {
46                 fx = Find(x);
47                 fy = Find(y);
48                 if(fx == fy && Rank[x] == Rank[y])
49                 {
50                     ans = false;
51                 }
52                 else if(fx != fy)
53                 {
54                     Par[fx] = fy;
55                     Rank[fx] = Rank[x]^(Rank[y]^1);
56                 }
57             }
58         }
59         if(ans)
60         {
61             printf("Scenario #%d:
No suspicious bugs found!
", Cnt);
62         }
63         else
64         {
65             printf("Scenario #%d:
Suspicious bugs found!
", Cnt);
66         }
67     }
68     return 0;
69 }

View Code