#23074: DFS 哪裡寫錯了嗎


pink_banana (pink_banana)

學校 : 臺北市立第一女子高級中學
編號 : 135688
來源 : [111.243.97.229]
最後登入時間 :
2021-08-31 00:55:18
d768. 10004 - Bicoloring -- UVa10004 | From: [111.71.8.117] | 發表日期 : 2020-10-21 01:07

試了好多次都是 WA: line 103
後來把DFS換成BFS居然就AC了
所以下面的DFS函數到底哪裡寫錯了?
請大家路過幫忙看看吧

#include <cstdio> #include <cstdlib> #include <vector> using namespace std; vector < vector <int> > adj; bool *visit; bool *color; bool DFS(int i) { for (int j = 0; j < adj[i].size(); j++) { if (!visit[adj[i][j]]) { visit[adj[i][j]] = true; color[adj[i][j]] = !color[i]; DFS(adj[i][j]); } else if (color[adj[i][j]] == color[i]){ return false; } } return true; } int main() { int n, m, a, b; adj.reserve(200); while (scanf("%d", &n) && n) { adj.resize(n); visit = (bool *)calloc(n, sizeof(bool)); color = (bool *)calloc(n, sizeof(bool)); scanf("%d", &m); for (int i = 0; i < m; i++) { scanf("%d %d", &a, &b); adj[a].push_back(b); adj[b].push_back(a); } visit[0] = true; color[0] = true; if (DFS(0)) printf("BICOLORABLE.\n"); else printf("NOT BICOLORABLE.\n"); adj.clear(); free(visit); free(color); } return (0); }
 
ZeroJudge Forum