算法練習：hiho 1122 二分圖最大匹配 (BFS 建圖 + 匈牙利算法)

問題抽象

給定無向圖，判斷是否為二分圖，若是則求最大匹配數。關鍵步驟：

1. BFS 染色構造二分圖（相鄰節點不同色）
2. 對左側節點跑匈牙利算法尋找增廣路

BFS 二分圖檢查與染色

bool bfs(int start) {
    queue q; q.push(start);
    color[start] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (color[v] == color[u]) return false; // 奇環，非二分圖
            if (color[v] == -1) {
                color[v] = 1 - color[u];
                q.push(v);
            }
        }
    }
    return true;
}

匈牙利算法核心

bool dfs(int u) {
    for (int v : adj[u]) if (!vis[v]) {
        vis[v] = true;
        if (match[v] == -1 || dfs(match[v])) {
            match[v] = u;
            return true;
        }
    }
    return false;
}

// 主流程
int ans = 0;
for (int u=1; u<=n; u++) if (color[u]==0) { // 只遍歷左側
    memset(vis, 0, sizeof(vis));
    if (dfs(u)) ans++;
}

完整代碼結構

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

const int MAXN = 10010;
vector adj[MAXN];
int color[MAXN], match[MAXN], vis[MAXN];
int n, m;

int main() {
    cin >> n >> m;
    for (int i=0; i> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    memset(color, -1, sizeof(color));
    bool ok = true;
    for (int i=1; i<=n; i++) if (color[i]==-1)
        if (!bfs(i)) { ok=false; break; }
    if (!ok) { cout << "No" << endl; return 0; }
    memset(match, -1, sizeof(match));
    int ans = 0;
    for (int i=1; i<=n; i++) if (color[i]==0) {
        memset(vis, 0, sizeof(vis));
        if (dfs(i)) ans++;
    }
    cout << ans << endl;
    return 0;
}

心得總結

• 大問題拆解：①構造二分圖 ②最大匹配，分而治之
• 鄰接表存儲圖，BFS 染色同時檢查二分性
• 匈牙利算法 DFS 尋找增廣路，每找到一條匹配數 +1
• 數據結構選擇關鍵：vector 邊表、顏色數組、匹配數組、訪問標記