給定一度數序列判斷是否可構成一簡單無向圖

題目

解法一 : Erdős–Gallai Theorem

若一 n 點簡單圖的度數序列為

$d_1\ge d_2\ge ...\ge d_n\ge 0$

$$⟺\sum _{i=1}^n{d}_i\mathrm{為}\mathrm{偶}\mathrm{數}，\mathrm{且}\sum _{i=1}^k{d}_i\le k(k-1)+\sum _{i=k+1}^{n}min(d_i,k),foreverykin1\le k\le n$$

如果直接套入定理算 k 從 1 跑到 n，時間複雜度會是

$O(n^2)$，因為右手邊的總和會一直重複計算到，所以實作時要記錄累計的總和來提升效率。另外這題需要先對給定度數序列進行排序，我們已知排序時間複雜度為 O(nlogn)，但這裡可以利用度數序列的特性來讓排序更快。因為合法度數的範圍是 0 ~ n-1，所以可以利用 Counting Sort 來讓排序只要 O(n)。最後分析 ErdosGallai() 的時間複雜度，Line 15-18 每回合最多只會將 pos 減 1，Line 22-25 每回合最多只會將 pos 加 1，當 pos = k 時，pos 不會改變。因此 ErdosGallai() 的時間複雜度為 O(n)。

故整體時間複雜度為 O(n)。

實作

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

bool ErdosGallai(const vector<int> &deg) {
    ll LHS = 0, RHS, N = deg.size(), suffix = 0;
    ll pos = N; // suffix = deg[pos] + ... deg[N-1]

    for (int k = 1; k <= N; ++k) {
        LHS += deg[k - 1];
        RHS = k * (k - 1LL);

        // 由後往前加，在算公式的右手邊加總 for min(di, k) = di
        // 每回合 pos 最多只減一次
        while (pos - 1 >= k && deg[pos - 1] < k) {
            suffix += deg[pos - 1];
            pos--;
        }

        // 公式左手邊，因為 pos 的位置比 k 還要前面了，所以要將之前多加的項要扣除
        // 每回合 pos 最多只加一次，因為 pos 和 k 最多差 1
        while (pos < k) {
            suffix -= deg[pos];
            pos++;
        }

        RHS += suffix;

        // min(di, k) = k，因為是由大到小排序所以可以一次處理 deg 超過 k 的部分
        if (pos > k) RHS += (pos - k) * k; 
        if (LHS > RHS) return false;
    }

    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    // cnt 計算度數頻率，Counting Sort 要用
    vector<int> deg, cnt;
    int N;

    while (cin >> N, N) {
        deg.clear();
        deg.reserve(N);
        cnt.assign(N, 0);

        ll sum = 0;
        int mx = 0;
        bool isSimple = true;

        for (int i = 0; i < N; ++i) {
            int tmp;
            cin >> tmp;

            sum += tmp; // 計算左邊項 d1 + ... + di
            mx = max(mx, tmp); // 最大值拿來判斷用

            // 合法度數範圍 0 ~ N-1
            if (0 <= tmp && tmp < N) cnt[tmp]++;
            else {
                isSimple = false;
                break;
            }
        }
        
        if ((sum % 2 != 0) || (mx >= N)) isSimple = false;
        if(isSimple){
            // counting sort
            for (int i = N - 1; i >= 0; --i) {
                while (cnt[i]--)
                    deg.emplace_back(i); 
                    // push 進去的意思，但效率比 push_back() 好
            }

            if (!ErdosGallai(deg)) isSimple = false;
        }
        
        if (isSimple) cout << "Possible\n";
        else cout << "Not possible\n";
    }
}

• a443: 10720 - Graph Construction

解法二 : Havel–Hakimi Algorithm

有時間再寫