題目連結: https://zerojudge.tw/ShowProblem?problemid=d768
# 內容
判斷是否為二分圖
# 解題思路
運用 BFS 將相鄰的點都塗上與自己不同的色，如果已塗上色就需判斷是否相異，若相同則不是答案
# 程式碼
#include <bits/stdc++.h> | |
using namespace std; | |
vector <int> g[200]; | |
int color[200]; | |
int main() { | |
int n, m, u, v; | |
while (cin >> n && n){ | |
for (int i=0; i<n; i++){ | |
g[i].clear(); | |
color[i] = -1; | |
} | |
cin >> m; | |
for (int i=0; i<m; i++){ | |
cin >> u >> v; | |
g[u].push_back(v); | |
g[v].push_back(u); | |
} | |
queue <int> q; | |
q.push(0); | |
color[0] = 0; | |
bool BICOLORABLE = true; | |
while (!q.empty()){ | |
int now = q.front(); q.pop(); | |
for (auto nxt: g[now]){ | |
if (color[nxt] != -1){ | |
if (color[nxt] != color[now]) continue; | |
else { | |
BICOLORABLE = false; | |
break; | |
} | |
} else { | |
color[nxt] = color[now] ^ 1; | |
q.push(nxt); | |
} | |
} | |
if (!BICOLORABLE) break; | |
} | |
if (!BICOLORABLE) cout << "NOT BICOLORABLE.\n"; | |
else cout << "BICOLORABLE.\n"; | |
} | |
} |
