首页 > 代码库 > poj 1659 Frogs' Neighborhood (Havel-Hakimi定理,判断序列是否可图)

poj 1659 Frogs' Neighborhood (Havel-Hakimi定理,判断序列是否可图)

链接:poj 1659

中文题不必解释题意、、、

其实质是给定一个度序列,判断是否可图,

若可图,输出YES,并输出各顶点之间的连边的情况

否则,输出NO

思路:判断一个序列是否可图,直接利用Havel-Hakimi定理即可

判断任意一个序列是否可图的具体过程:

(1)先将序列由大到小排序

(2)设最大的度数为 t ,将最大项删除,然后把最大度数后

(不包括自己)的 t 个度数分别减1(意思就是把度数最大的点与后几个点连边)

(3)重复上述两步,如果最大度数t超过了剩下顶点的个数,

或者序列中出现了负数,则不可图,如果序列全部变为0,则可图。


#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct stu
{
    int d,id;
}frog[12];
int cmp(struct stu a,struct stu b)
{
    return a.d>b.d;
}
int main()
{
    int T,n,i,pos,j,k,edge[12][12],flag;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(i=1;i<=n;i++){
            scanf("%d",&frog[i].d);
            frog[i].id=i;
        }
        memset(edge,0,sizeof(edge));
        flag=1;
        pos=1;
        while(1){
            sort(frog+pos,frog+1+n,cmp);  //先由大到小排序
            k=frog[pos].d;               //找到最大项
            if(k==0)                  //若最大项为0,则序列全部为0
                break;
            if(pos+k>n){             //若最大度数超过了顶点的个数则不合理
                flag=0;
                break;
            }
            for(i=pos+1;i<=pos+k;i++){   //对最大项后的k项依次减一
                frog[i].d--;          
                edge[frog[pos].id][frog[i].id]=1;
                edge[frog[i].id][frog[pos].id]=1;
                if(frog[i].d<0){          //判断是否出现负度数
                    flag=0;
                    break;
                }
            }
            pos++;
        }
        if(!flag)
            printf("NO\n");
        else{
            printf("YES\n");
            for(i=1;i<=n;i++)
                for(j=1;j<=n;j++){
                    printf("%d",edge[i][j]);
                    if(j==n)
                        printf("\n");
                    else
                        printf(" ");
                }
        }
        if(T)
            printf("\n");
    }
    return 0;
}


poj 1659 Frogs' Neighborhood (Havel-Hakimi定理,判断序列是否可图)