Luogu-SP3377-BUGLIFE - A Bug's Life

Posted on Edited on Word count in article: 816

题目 BUGLIFE - A Bug's Life/原SPOJ

题目描述

就是一个奇怪的ke学家，他专门研究虫子是否存在同性恋。。。
他为没一只虫子都标上了序号。
通过这个奇怪的ke学家的研究，找出了在这些虫子中的所有关系的虫子，题目询问在这么多有关系的虫子中是否存在“同性恋”。

Professor Hopper is researching the sexual behavior of a rare species of bugs. He assumes that they feature two different genders and that they only interact with bugs of the opposite gender. In his experiment, individual bugs and their interactions were easy to identify, because numbers were printed on their backs.
Given a list of bug interactions, decide whether the experiment supports his assumption of two genders with no homosexual bugs or if it contains some bug interactions that falsify it.

输入格式

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

The first line of the input contains the number of scenarios. Each scenario starts with one line giving the number of bugs (at least one, and up to 2000) and the number of interactions (up to 1000000) separated by a single space. In the following lines, each interaction is given in the form of two distinct bug numbers separated by a single space. Bugs are numbered consecutively starting from one.

输出格式

对于每一组数据：
先输出：“Scenario #i” ，表示第ii组数据
然后如果有同性恋的输出"Suspicious bugs found!"
否则输出"No suspicious bugs found!"

The output for every scenario is a line containing “Scenario #i:”, where i is the number of the scenario starting at 1, followed by one line saying either “No suspicious bugs found!” if the experiment is consistent with his assumption about the bugs’ sexual behavior, or “Suspicious bugs found!” if Professor Hopper’s assumption is definitely wrong.

思路：邻接表/链式前向星

整体思路

首先考虑样例 1↔2,2↔3,1↔31 \leftrightarrow 2,2 \leftrightarrow 3,1 \leftrightarrow 3：

显然存在同性恋。为什么？

因为存在奇数个节点的环。

思考：如果一个环有奇数个节点，那么必定存在同性恋。

因为奇数意味着男女两种性别的数量不同，因此必定会有相同性别的点连通（有关系）。

代码转换

考虑以下流程：

  • 将 11 号点的性别标记为 00。对于每个和 11 连通（有关系）的点（22 和 33），将它们的性别标记为 11。

  • 22 号点标记过，所以直接遍历连通的点（33，因为 11 已经访问过了，所以不再访问）。

  • 因为 33 号点的性别和 22 号点的性别标记相同，所以认为：22 号点和 33 号点是同性恋的关系。

因为是从每个点出发，寻找所有连通的点，所以使用邻接表/链式前向星（保存了一个点出发的所有边）的方式。

具体流程

对于每一组数据，进行如下操作：

  • 初始化
  • 建图
  • 遍历 i∈[1,n]i \in \left[1,n\right] 的所有节点：
    • 如果没访问过 ii ，将其性别设为 00。
    • 访问每个与 ii 连通的点 toto。
      • 如果没访问过 toto，将其性别设为 1 xor to1 \ \mathrm{xor}\ to。
      • 如果访问过 toto，检查 ii 号点的性别与 toto 号节点的性别是否相同，相同则为同性恋。
  • 如果到最后也没有同性恋，则整个图中都没有同性恋。

AC Code

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
// template v4
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int inf = 0x7f7f7f7f;

const int N = 2024;
const int M = 2024000;
struct Edge {
    int to, next;
};

vector<Edge> edges;

int head[N];
int pt = 1;

bool mark[M];
bool vis[M];

int n, m;

void add_edge(int from, int to) {
    edges.push_back({to, head[from]});
    head[from] = pt;
    pt++;
}

void init() {
    memset(mark, 0, sizeof mark);
    memset(vis, 0, sizeof vis);
    memset(head, 0, sizeof head);
    pt = 1;
    edges.clear();
}

void get_str(int t) {
    cin >> n >> m;
    int t1, t2;
    edges.push_back({0, 0});
    for(int i = 0; i < m; i++) {
        cin >> t1 >> t2;
        add_edge(t1, t2);
        add_edge(t2, t1);
    }
    for(int i = 1; i <= n; i++) {
        if(!vis[i]) mark[i] = 0;
        for(int j = head[i]; j; j = edges[j].next) {
            int to = edges[j].to;
            if(!vis[to]) mark[to] = 1 ^ mark[i];
            if(mark[to] == mark[i]) {
                printf("Scenario #%d:\nSuspicious bugs found!\n", t);
                return;
            }
            if(vis[to]) continue;
            vis[to] = true;
        }
    }
    printf("Scenario #%d:\nNo suspicious bugs found!\n", t);
}

int main() {
    int t;
    cin >> t;
    for(int i = 1; i <= t; i++) {
        init();
        get_str(i);
    }
    return 0;
}