HDOJ 2454 Degree Sequence of Graph G：Havel-Hakimi 判斷簡單圖度序列

題目大意

給定非負整數序列，判斷是否存在無向簡單圖（無自環、無重邊）使其度序列恰為該序列。多測資，n < 1000。

Havel-Hakimi 定理

序列 d₁ ≥ d₂ ≥ ... ≥ dₙ 可圖實現 ⇔ 序列 d₂-1, d₃-1, ..., d_{d₁+1}-1, d_{d₁+2}, ..., dₙ（去掉 d₁，其餘前 d₁ 個各減 1，重新排序）可圖實現。遞歸直到全 0（可行）或出現負數/度數 ≥ 剩餘節點數（不可行）。

代碼實現

#include <bits/stdc++.h>
using namespace std;

int a[10010];

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n; scanf("%d", &n);
        long long sum = 0;
        for (int i = 0; i < n; ++i) { scanf("%d", &a[i]); sum += a[i]; }
        if (sum % 2) { puts("no"); continue; }
        bool ok = true;
        for (int i = 0; i < n; ++i) if (a[i] >= n) { ok = false; break; }
        if (!ok) { puts("no"); continue; }

        while (true) {
            sort(a, a + n, greater());
            if (a[0] == 0) break; // 全零
            int d = a[0];
            if (d >= n) { ok = false; break; }
            for (int i = 1; i <= d; ++i) {
                if (--a[i] < 0) { ok = false; break; }
            }
            a[0] = 0;
            if (!ok) break;
        }
        puts(ok ? "yes" : "no");
    }
    return 0;
}

複雜度

• 每輪排序 O(n log n)，至多 n 輪，總 O(n² log n)，n ≤ 1000 可接受。
• 可用計數排序優化至 O(n²)。

關鍵檢查

1. 度數和必為偶數（握手定理）。
2. 任意度數 ≥ n 直接不可行（簡單圖最大度 n-1）。
3. 減 1 過程中出現負數 → 不可行。

範例

6: 4 4 3 3 2 2 → yes
4: 2 1 1 1 → no

Havel-Hakimi 算法是判斷圖度序列的經典方法，實現簡單且直觀。