题解 [email protected]洛谷 | [email protected] 【BUGLIFE - A Bug’s Life】

很久以前 AC 了这题,现在补一个题解。

题意简述:有若干个虫子,它们之间有一些关♂系,要判断它们之间有没有同性恋。

那么什么情况会出现同性恋呢?题目中有关系的虫子连成一个无向图,如果有长度为奇数的环,那么一定有同性恋;如果不存在长度为奇数的环,那么也不一定存在同性恋。大家可以画个图理解一下。

于是原题转换为:给定一个无向图,求图中是否有长度为奇数的环。

看到其他题解都在写种类并查集,我们来个简单的,新手也可以看懂的方法——0/1 染色 dfs

我们这里将虫子划分为两类:“颜色”(这里代表性别)为 1122,用 00 表示还没有搜索到。每一次遍历从当前点 uu 为起点的所有的边 e(u,v)e(u,v),如果 uuvv 颜色相同,意味着有同性恋。如果 vv 没有被染色,那么 dfs 到 vv,颜色取反(3col3-col)。

时间复杂度分析:对于每一组数据,每个点最多被遍历(染色)一次,所以时间复杂度为 O(n)O(n);原题有 TT 组数据,时间复杂度为 O(Tn)O(Tn),可以通过此题。

代码(有一些注释):

//By: [email protected]_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;
}