2319.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2319 on 2006-08-13 at 20:12:13 */ 
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
const int N = 2048;
 
vector<int> g[N];
int n, col[N];
 
bool bit(int);
 
int main()
{
	int t, T, i;
	
	scanf("%d", &T);
	for(t = 1; t <= T; t++) {
		int m; scanf("%d %d", &n, &m);
		for(i = 0; i < n; i++) g[i].clear();
		for(i = 0; i < m; i++) {
			int a, b; scanf("%d %d", &a, &b);
			g[a-1].push_back(b-1); g[b-1].push_back(a-1);
		}
		memset(col, 0, sizeof(col));
		bool can = true;
		for(i = 0; i < n && can; i++)
			if(col[i] == 0) can = bit(i);
		printf("Scenario #%d:\n", t);
		if(can) printf("No suspicious bugs found!\n\n");
		else printf("Suspicious bugs found!\n\n");
	}
	
	return 0;
}
 
bool bit(int k)
{
	int i, stack[N], top = 0;
	stack[top++] = k; col[k] = 1;
	while(top > 0) {
		int p = stack[--top];
		for(i = g[p].size()-1; i >= 0; i--) {
			int x = g[p][i];
			if(col[x] == col[p]) return false;
			else if(col[x] == 0) {
				col[x] = -col[p];
				stack[top++] = x;
			}
		}
	}
	return true;
}