POJ 1659 Frogs Neighborhood

分析：切圖論切的第一道題、也是圖論的例題、主要用到一個Havel-Hakimi 定理 有以下兩種不合理的情形： (1) 某次對剩下序列排序後，最大的度數（設為d1）超過了剩下的頂點數； (2) 對最大度數後面的d1 個度數各減1 後，出現了負數。

#include<stdio.h>  
#include<stdlib.h>  
#include<string.h>  
#define N 15  
struct vertex{  
    int degree;//頂點的度  
    int index;//頂點序號  
}v[N];  
int cmp(const void *a,const void *b){  
    return ((vertex*)b)->degree-((vertex*)a)->degree;  
}  
int main(){  
    int t,n,i,j,k,r,p,q,d1;  
    int Edge[N][N],flag;  
    scanf("%d",&t);  
    while(t--){  
        scanf("%d",&n);  
        for(i=0;i<n;i++){  
            scanf("%d",&v[i].degree);  
            v[i].index=i;  
        }  
        memset(Edge,0,sizeof(Edge));  
        flag=1;  
        for(k=0;k<n&&flag;k++){  
            qsort(v+k,n-k,sizeof(vertex),cmp);  
            i=v[k].index;  
            d1=v[k].degree;  
            if(d1>n-k-1)flag=0;  
            for(r=1;r<=d1&&flag;r++){  
                j=v[k+r].index;  
                if(v[k+r].degree<=0)flag=0;  
                v[k+r].degree--;  
                Edge[i][j]=Edge[j][i]=1;  
            }  
        }  
        if(flag){  
            puts("YES");  
            for(p=0;p<n;p++){  
                for(q=0;q<n;q++){  
                    if(q)printf(" ");  
                    printf("%d",Edge[p][q]);  
                }  
                puts("");  
            }  
        }  
        else puts("NO");  
        if(t) puts("");  
    }  
    return 0;  
}