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; }