POJ 1659 Frogs' Neighborhood：度數序列構造無向圖（Havel-Hakimi 算法）

問題描述

給定 n（2 < n < 10）個節點的度數 x_1..x_n。判斷是否存在無向簡圖實現此度數序列。若存在，輸出任意一個鄰接矩陣；否則輸出 NO。多測試用例。

Havel-Hakimi 算法

1. 將度數與節點索引綁定，按度數降序排序。
2. 取度數最大的節點 u（度 d），將其度設為 0。
3. 選取下一個度數最大的 d 個節點，各自度數減 1，並在鄰接矩陣中連邊 u-v。
4. 若過程中出現度數 < 0，或剩餘節點不足 d 個，則無解。
5. 重複直到所有度數為 0。

正確性

該算法基於圖論定理：一個非負整數序列是圖度數序列的充要條件是經過 Havel-Hakimi 歸約後全為 0。構造過程即給出具體圖。

代碼實現

#include 
#include 
#include 
struct Node { int mark, deg; } a[22];
int mat[22][22];

int cmp(const void* a, const void* b) {
    return ((Node*)b)->deg - ((Node*)a)->deg;
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n; scanf("%d", &n);
        memset(mat, 0, sizeof(mat));
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i].deg);
            a[i].mark = i;
        }
        bool ok = true;
        for (int k = 0; k < n; k++) {
            qsort(a, n, sizeof(Node), cmp);
            if (a[k].deg == 0) break;
            if (a[k].deg > n - k - 1) { ok = false; break; }
            for (int i = 1; i <= a[k].deg; i++) {
                a[k+i].deg--;
                if (a[k+i].deg < 0) { ok = false; break; }
                mat[a[k].mark][a[k+i].mark] = mat[a[k+i].mark][a[k].mark] = 1;
            }
            if (!ok) break;
        }
        if (!ok) printf("NO\n");
        else {
            printf("YES\n");
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++)
                    printf("%d%c", mat[i][j], j==n-1?'\n':' ');
            }
        }
        if (T) printf("\n");
    }
    return 0;
}

注意事項

• 每次選取最大度數節點前必須重新排序。
• 輸出矩陣行列對應原始節點編號（mark）。
• 測試用例間輸出空行。