题解 SP3377 【BUGLIFE - A Bug’s Life】

rui_er

2020-08-24 09:57:18

Solution

很久以前 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; } ```