題目大意

給定一個度序列，問這個度序列是否能構成一張簡單圖？

題解

這一題與 1210. 圖論 之 簡單圖測試 其實差不多，但是要求的 n 更大了，因此需要實作線性演算法。

這裡使用 Erdős–Gallai theorem 來完成。

  • Erdős–Gallai theorem
    若度序列 d:d1≥d2≥…dn 是圖序列 ⟺ ∑d 是偶數，且對於 1≤k≤n 都有
∑i=1kdi≤k(k−1)+∑j=k+1nmin{k,dj}

簡單來說，就是把 k=1∼n 都帶入公式即可。但如果每一次都要重算，會需要 O(n2) 的時間，因此這裡把等式左右邊的數值都好好的保存下來並維護。

左半邊的部分比較簡單。右半邊的部分，如果大於 k，就只加上 k。因此我們先使用 Counting sort 把資料由大到小排序後，再認真的紀錄可以直接加起來的區間。由於度序列合法的值域為 0∼n−1，因此排序的步驟是 O(n) 的。

這一個加總區間的變化較特別，一開始會向右擴張，再隨著 k 變大，又會逐漸地向左收縮。由於每一個數字只會被加入或移除一次，因此區間的維護成本是平攤 O(1) 的，總時間複雜度就能控制在 O(n) 完成。

AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

bool ErdosGallai(const vector<int> &deg) {
    ll LHS = 0, RHS;

    ll N = deg.size();
    ll 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); // k <= 100'0000

        while (pos - 1 >= k && deg[pos - 1] < k) {
            suffix += deg[pos - 1];
            pos--;
        }

        while (pos < k) {
            suffix -= deg[pos];
            pos++;
        }
        RHS += suffix;

        if (pos > k)
            RHS += (pos - k) * k;

        if (LHS > RHS)
            return false;
    }

    return true;
}

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

    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;

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

            sum += tmp;
            mx = max(mx, tmp);

            if (0 <= tmp && tmp < N)
                cnt[tmp]++;
        }

        bool isSimple = true;
        do {
            if (sum % 2 != 0) {
                isSimple = false;
                break;
            }

            if (mx >= N) {
                isSimple = false;
                break;
            }

            // counting sort
            for (int i = N - 1; i >= 0; --i) {
                while (cnt[i]--)
                    deg.emplace_back(i);
            }

            if (!ErdosGallai(deg)) {
                isSimple = false;
                break;
            }
        } while (false);

        if (isSimple)
            cout << "Possible\n";
        else
            cout << "Not possible\n";
    }
}

OJ 連結

連結：https://zerojudge.tw/ShowProblem?problemid=a443