题解 SP3377 【BUGLIFE - A Bug’s Life】
rui_er
2020-08-24 09:57:18
很久以前 AC 了这题,现在补一个题解。
题意简述:有若干个虫子,它们之间有一些关♂系,要判断它们之间有没有同性恋。
那么什么情况会出现同性恋呢?题目中有关系的虫子连成一个无向图,如果有长度为奇数的环,那么一定有同性恋;如果不存在长度为奇数的环,那么也不一定存在同性恋。大家可以画个图理解一下。
于是原题转换为:给定一个无向图,求图中是否有长度为奇数的环。
看到其他题解都在写种类并查集,我们来个简单的,新手也可以看懂的方法——**0/1 染色 dfs**。
我们这里将虫子划分为两类:“颜色”(这里代表性别)为 $1$ 或 $2$,用 $0$ 表示还没有搜索到。每一次遍历从当前点 $u$ 为起点的所有的边 $e(u,v)$,如果 $u$ 和 $v$ 颜色相同,意味着有同性恋。如果 $v$ 没有被染色,那么 dfs 到 $v$,颜色取反($3-col$)。
时间复杂度分析:对于每一组数据,每个点最多被遍历(染色)一次,所以时间复杂度为 $O(n)$;原题有 $T$ 组数据,时间复杂度为 $O(Tn)$,可以通过此题。
代码(有一些注释):
```cpp
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
const int N = 2005, M = (int)(1e6+5)<<1;
int T, n, m, ans;
int col[N];
struct Edge { // 前向星建图
int v, nxt;
Edge() {}
Edge(int a, int b) : v(a), nxt(b) {}
}e[M];
int ne, h[N];
void add(int u, int v) {
e[++ne] = Edge(v, h[u]);
h[u] = ne;
e[++ne] = Edge(u, h[v]);
h[v] = ne;
}
void dfs(int u, int c) { // 0/1 染色 dfs,两个参数分别是当前点编号和颜色
col[u] = c;
for(int i=h[u];i;i=e[i].nxt) {
int v = e[i].v;
if(col[v] == col[u]) {
ans = 0;
break;
}
if(!col[v]) {
dfs(v, 3-c);
}
}
}
int main() {
scanf("%d", &T);
for(int _=1;_<=T;_++) {
memset(e, 0, sizeof(e));
memset(h, 0, sizeof(h));
memset(col, 0, sizeof(col));
ne = 0;
ans = 1;
printf("Scenario #%d:\n", _);
scanf("%d%d", &n, &m);
for(int i=1;i<=m;i++) {
int u, v;
scanf("%d%d", &u, &v);
add(u, v);
}
for(int i=1;i<=n;i++) { // 对于每一个未被染色的点(新连通块),进行 dfs,与 tarjan 算法类似
if(ans && !col[i]) {
dfs(i, 1);
}
}
if(ans) {
puts("No suspicious bugs found!");
}
else {
puts("Suspicious bugs found!");
}
}
return 0;
}
```