UVA 10004 Bicoloring - 二分圖判定（BFS/DFS）

問題描述

給定無向圖，判斷是否為二分圖（即能否用兩種顏色給頂點著色，使相鄰頂點顏色不同）。輸入多組測試，每組給出邊數，以 0 結束。

解法：BFS 著色

從任意未著色頂點開始 BFS，賦色 1，鄰節點賦色 -1。若發現鄰節點已著色且顏色相同，則不是二分圖。圖可能不連通，需對每個連通分量檢查。

代碼實現（C++）

#include 
#include 
#include 
#include 
using namespace std;

const int MAXN = 205;
vector G[MAXN];
int color[MAXN];

bool bfs(int start) {
    queue q;
    q.push(start);
    color[start] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : G[u]) {
            if (color[v] == 0) {
                color[v] = -color[u];
                q.push(v);
            } else if (color[v] == color[u]) {
                return false;
            }
        }
    }
    return true;
}

int main() {
    int n, m;
    while (cin >> n && n) {
        cin >> m;
        for (int i=0;i> u >> v;
            G[u].push_back(v);
            G[v].push_back(u);
        }
        memset(color, 0, sizeof(color));
        bool ok = true;
        for (int i=0;i

DFS 遞歸版
同理，用遞歸實現著色，注意棧深度（n≤200 安全）。

複雜度
時間 O(V+E)，空間 O(V+E)。