HDU 4751 Divide Groups：二分圖判斷（互不認識建圖染色）

問題描述

n 人參加活動，需分成兩組，使每組內部任意兩人互相認識（即每組是完全圖）。判斷是否可行。

解題思路

若兩人不互相認識（單向或都不認識），則他們不能在同一組。建立「不互相認識」圖：若 i 不認識 j 或 j 不認識 i，連無向邊。問題轉化為：該圖是否為二分圖。用 BFS/DFS 染色判斷。

代碼實現 (C++)

#include 
using namespace std;
const int MAXN = 105;
vector G[MAXN];
int color[MAXN];
bool bfs(int n) {
    fill(color, color+n+1, -1);
    for (int i = 1; i <= n; ++i) if (color[i] == -1) {
        color[i] = 0;
        queue q; q.push(i);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : G[u]) {
                if (color[v] == -1) { color[v] = color[u]^1; q.push(v); }
                else if (color[v] == color[u]) return false;
            }
        }
    }
    return true;
}
int main() {
    int n;
    while (cin >> n) {
        for (int i = 1; i <= n; ++i) G[i].clear();
        vector> know(n+1, vector(n+1, 0));
        for (int i = 1; i <= n; ++i) {
            int x;
            while (cin >> x && x) know[i][x] = 1;
        }
        for (int i = 1; i <= n; ++i)
            for (int j = i+1; j <= n; ++j)
                if (!know[i][j] || !know[j][i]) {
                    G[i].push_back(j); G[j].push_back(i);
                }
        cout << (bfs(n) ? "YES" : "NO") << endl;
    }
    return 0;
}

複雜度分析

• 時間複雜度：O(n^2) 建圖 + O(n+m) 染色，n≤100 極快。
• 空間複雜度：O(n^2)。

總結

將「組內完全圖」條件轉化為「補圖為二分圖」，是典型的圖論建模技巧。二分圖染色模板熟練掌握。