Havel-Hakimi定理（握手定理）
由非负整数组成的非增序列s（度序列）：d1，d2，…，dn（n>=2，d1>=1）是可图的，当且仅当序列：
s1:d2 – 1，d3 – 1，…，dd1+1 – 1，dd1+2，…，dn
是可图的。序列s1中有n-1个非负整数，s序列中d1后的前d1个度数（即d2~dd1+1）减1后构成s1中的前d1个数。
说白了就是先把第一个点（度数为d1）连线到后面d1个点，保证第一个点度数满足，然后再以此类推考虑后面的点。如果后面所有顶点满足并且度数不多不少（最后不剩，过程中没有度数为负数），即可认为，度序列是可图的。
为什么每一次都要排成非递增序列后再操作？因为这样是最好判断的，最后都成0就可图，中途出现负数就不可图。如果不排成非递增就不好判断了，比如最后0，1，0，1是可图的；0，2，0，2不可图，还有各种最终情况，很难写代码去判断可图不可图。
由同一个可图序列构造出来的图不一定是唯一的。
例题poj1659
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<cmath> #include<map> #include<set> #include<list> #include<deque> #include<vector> #include<algorithm> #include<stack> #include<queue> #include<cctype> #include<sstream> using namespace std; #define pii pair<int,int> #define LL long long int const double eps=1e-10; const int INF=1000000000; const int maxn=10+3;int ans[maxn][maxn]; int T,n; struct node {int id,de; } x[maxn];bool cmp(node a,node b) {return a.de>b.de; }int main() {//freopen("in1.txt","r",stdin);//freopen("out.txt","w",stdout);scanf("%d",&T);while(T--){scanf("%d",&n);for(int i=0; i<n; i++){scanf("%d",&x[i].de);x[i].id=i+1;}memset(ans,0,sizeof(ans));int tn=n;bool can=1;while(tn>0){sort(x,x+n,cmp);if(x[0].de==0) break;for(int i=1; i<=x[0].de; i++){if(x[i].de>0&&i<n){x[i].de--;ans[x[0].id][x[i].id]=ans[x[i].id][x[0].id]=1;}else{can=false;break;}}if(can==false) break;x[0].de=0;tn--;}if(can==true){puts("YES");for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(j==1) printf("%d",ans[i][j]);else printf(" %d",ans[i][j]);}puts("");}}else puts("NO");if(T>=1) puts("");}//fclose(stdin);//fclose(stdout);return 0; }
