POJ_2492 A Bug's Life

問題
解法
グラフの2彩色判定をすればいい。深さ優先探索を用いるとできた。
コードに無駄ありすぎぃな感がある。

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_N = 2000;
int T, N, M;
bool interact[MAX_N][MAX_N];
bool used[MAX_N];
char color[MAX_N];
bool c(int v, int col){
	used[v] = true;
	color[v] = col;
	for(int u = 0; u < N; u++){
		if(interact[v][u]){
			if(used[u]){
				if(color[u] != (col+1) % 2)
					return false;
			}else{
				if(!c(u, (col+1)%2))
					return false;
			}
		}
	}
	return true;
}
int main(){
	scanf("%d", &T);
	for(int t = 0; t < T; t++){
		scanf("%d %d", &N, &M);
		fill(used, used+MAX_N, false);
		fill(color, color+MAX_N, 3);
		for(int i=0;i<N;i++)
			for(int j=0;j<N;j++)
				interact[i][j] = false;
		for(int i = 0; i < M; i++){
			int a, b;
			scanf("%d %d", &a, &b);
			a--; b--;
			interact[a][b] = true;
			interact[b][a] = true;
		}
		bool f = true;
		for(int i = 0; i < N; i++){
			if(!used[i])
				if(!c(i, 0)){
					f=false;
					break;
				}
		}
		printf("Scenario #%d:\n", t+1);
		if(f)
			printf("No suspicious bugs found!\n");
		else
			printf("Suspicious bugs found!\n");
		if(t != T-1)
			puts("");
	}
	return 0;
}