POJ 1659 Frogs' Neighborhood - c++编程基础

分析：切图论切的第一道题、也是图论的例题、主要用到一个Havel-Hakimi 定理

有以下两种不合理的情形：

(1) 某次对剩下序列排序后，最大的度数（设为d1）超过了剩下的顶点数；

(2) 对最大度数后面的d1 个度数各减1 后，出现了负数。


#include  
#include  
#include  
#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-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