HDU 5285 wyh2000 and pupil：二分圖染色與 BFS 實戰

問題描述

給定一個無向圖，要求將頂點分成兩組，使得每組內部沒有邊相連（即二分圖判定）。同時每組至少要有一個頂點。若圖不是二分圖，或無法滿足「每組至少一個頂點」的條件，則無解。題目實際上是經典的二分圖染色問題，並要求統計兩組頂點的最大/最小值之和等變體。

核心思路：BFS + 二染色

使用 BFS 遍歷圖，嘗試將相鄰頂點染成不同顏色（1 和 -1）。若發現衝突（相鄰頂點同色），則圖不是二分圖，直接輸出 "Poor wyh"。若成功染色，則統計兩顏色的頂點數，根據題目要求計算答案。

關鍵細節

• 孤立點處理：若圖中有孤立點（度為 0），它可以任意分配，但需確保兩組非空。
• 特殊情況：當 n < 2 時無解；當圖中無邊時，一組 n-1，另一組 1。
• 連通分量：對每個未訪問的頂點啟動 BFS，累加各分量的兩色計數。

代碼框架 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
vector<int> G[MAXN];
int color[MAXN]; // 0=未訪問, 1/-1=兩種顏色
int n, m;

bool bfs(int start) {
    queue<int> q;
    q.push(start);
    color[start] = 1;
    int cnt1 = 0, cnt2 = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (color[u] == 1) cnt1++; else cnt2++;
        for (int v : G[u]) {
            if (color[v] == 0) {
                color[v] = -color[u];
                q.push(v);
            } else if (color[v] == color[u]) {
                return false; // 衝突，非二分圖
            }
        }
    }
    // 根據題目具體要求處理 cnt1, cnt2
    return true;
}

int main() {
    while (cin >> n >> m) {
        for (int i=1;i<=n;i++) G[i].clear(), color[i]=0;
        for (int i=0;i<m;i++) {
            int u,v; cin>>u>>v;
            G[u].push_back(v);
            G[v].push_back(u);
        }
        bool ok = true;
        // 遍歷所有連通分量
        for (int i=1;i<=n && ok;i++)
            if (color[i]==0) ok = bfs(i);
        if (!ok) cout << "Poor wyh" << endl;
        else {
            // 輸出答案
        }
    }
    return 0;
}

複雜度

時間 O(n+m)，空間 O(n+m)，完全滿足限制。

總結

二分圖染色是圖論基礎，BFS 實現簡潔高效。關鍵在於正確處理孤立點、多連通分量以及「每組至少一個頂點」的約束。本題是典型的模板題，掌握後可應用於許多變體問題。