SP3377《A Bug's Life》

十月 20, 2018 2423

谁闲的没事研究同性恋。。。

题目地址

本文同步发布于：Handwer’s 洛谷博客

题目大意

就是一个奇怪的ke学家，他专门研究虫子是否存在同性恋。。。

他为每一只虫子都标上了序号。

通过这个奇怪的ke学家的研究，找出了在这些虫子中的所有关系的虫子，题目询问在这么多有关系的虫子中是否存在“同性恋”。

输入格式 & 样例

第一行， 输入一个数，表示有t组数据
对于每组数据，第一行输入n,m，表示有n只虫子，有m个关系
接下来行每行两个数x,y，表示x,y有关系

1
2
3
4
5
6
7
8
2
3 3
1 2
2 3
1 3
4 2
1 2
3 4

输出格式 & 样例

对于每一组数据：

先输出：”Scenario #i” ，表示第i组数据

然后如果有同性恋的输出”Suspicious bugs found!”

否则输出”No suspicious bugs found!” 

1
2
3
4
Scenario #1:
Suspicious bugs found!
Scenario #2:
No suspicious bugs found!

解析

显然这是一个并查集，但并不是一个裸的并查集

我们要多维护一个数组rel[]，其中rel[i]表示i和它的祖先的关系（relative）。我们定义rel[i]表示两种性别，当根节点相同且rel[]相同时，它们就是同性恋

rel[]的更新方式：

1
2
(in Find(x))
rel[x] = (rel[x] + rel[U[x]]) % 2;
1
2
3
4
(in Union(x, y))
int fx = Find(x), fy = Find(y);
...
rel[fx] = (rel[x] + rel[y] + 1) % 2;

rel[]的判断方式：

1
2
3
4
5
(in Union(x, y))
if (fx == fy) {
	if (rel[x] == rel[y]) suspiciousFound = true;
    return;
}

剩下的照常写就行

注意路径压缩要分开写，先创建一个变量存它的祖先节点再更新

按秩合并没写过不知道

代码实现

你们最喜欢的代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXM = 1000000 + 10;

int n, m;
int U[MAXM], rel[MAXM];

bool flag;

int Find(int x) {
    if (x != U[x]) {
    	// 把路径压缩撑开写
        int fux = Find(U[x]);
        rel[x] = (rel[x] + rel[U[x]]) % 2; // 更新rel数组
        // 1 1 -> 0
        // 1 0 / 0 1 -> 1
        // 0 0 -> 0
        // 其实是一个异或的过程
        U[x] = fux； // qwq
    }
    return U[x];
}

void Union(int x, int y) {
    int fx = Find(x), fy = Find(y);
    if (fx == fy) {
        if (rel[x] == rel[y]) flag = true; // 判断是否同性
        return;
    }
    U[fx] = fy;
    rel[fx] = (rel[x] + rel[y] + 1) % 2; // 更新rel数组
}

int main(int argc, char *const argv[]) {
    int t;
    scanf("%d", &t);
    int _t = 0;
    while (t --> 0) {
        memset(U, 0, sizeof(U));
        memset(rel, 0, sizeof(rel));
        n = 0, m = 0, flag = false;
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= n; ++i) U[i] = i;
        for (int i = 1; i <= m; ++i) {
            int x, y;
            scanf("%d %d", &x, &y);
            Union(x, y);
        }
        printf("Scenario #%d:\n", ++_t);
        if (flag) printf("Suspicious bugs found!\n");
        else printf("No suspicious bugs found!\n");
    }
    return 3; // qwq
}