連結：https://tioj.ck.tp.edu.tw/problems/1210

題目大意

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

題解

最近恰好讀了圖論的書，若一個度序列可以構造出一個簡單圖，該序列又可稱為圖序列，利用度序列判定是否為簡單圖(無自環、重邊)在這本書【演算法觀點的圖論】第一章就有提到了，有兩個定理可以使用：

Erdős–Gallai theorem

若度序列 $d : d_{1} \geq d_{2} \geq \dots d_{n}$ 是圖序列 $⟺$ $\sum d$ 是偶數，且對於 $1 \leq k \leq n$ 都有

\sum_{i = 1}^{k} d_{i} \leq k (k - 1) + \sum_{j = k + 1}^{n} min {k, d_{j}}

Havel–Hakimi algorithm

對於 $n \geq 2$ ，若度序列 $d : d_{1} \geq d_{2} \geq \dots d_{n}$ 是圖序列 $⟺$

d^{'} : d_{2} - 1, d_{3} - 1, \dots, d_{1 + d_{1}} - 1, d_{2 + d_{1}}, d_{2 + d_{1}}, \dots, d_{n}

也是圖序列

可以發現第二個方法比較好實作，就是把度數最大的點，都接一條邊到度數較多的邊上。由於數字都是整數，可以利用 Counting Sort 或是一些技巧，就能在 $O (V)$ 的時間判定是否為簡單圖了。

AC Code

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

int c[10001];
int tmp[10001];
bool test(int mx)
{
    memset(tmp,0,sizeof(tmp));
    while( mx > 0 )
    {
        int req = mx, la = mx;
        c[mx]--;
        while(req>0&&la>0)
        {
            int del = min(c[la],req);
            c[la]-=del;
            tmp[la-1]+=del;
            req-=del;
            la--;
        }
        if( req ) return false;
        while(la<=mx)
        {
            c[la]+=tmp[la];
            tmp[la]=0;
            la++;
        }
        while( !c[mx] ) mx--;
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, tmp;
    
    while(cin>>N,N)
    {
        int deg=0;
        int mx=0;
        memset(c,0,sizeof(c));
        bool isSimple = true;
        
        for(int i=0;i<N;++i)
        {
            cin>>tmp;
            deg+=tmp;
            mx=max(mx,tmp);
            c[tmp]++;
        }
        
        if( deg%2!=0 ) isSimple = false;
        else if( mx >= N ) isSimple = false;
        else if( !test(mx) ) isSimple = false;
        
        if( isSimple )cout<<"Yes\n";
        else cout<<"No\n";
    }
}