首页 > 代码库 > HDU 2454 Degree Sequence of Graph G (可简单图化的判定 havel定理)

HDU 2454 Degree Sequence of Graph G (可简单图化的判定 havel定理)

题目链接:HDU 2454 Degree Sequence of Graph G

题意:给出N个点的度(简单图),问能能否画出个图,(其实就是给出一个串非负的序列是否有对应的图存在)

没见过这个定理 题意真的难懂。

havel定理就是一个给出一串非负的序列,存在一个无向图使得图中各点的度与此序列一一对应,则称此序列可图化。简单图的话就是,可简单图化。

可简单图化的判定(Havel定理):把序列排成不增序,即d1>=d2>=……>=dn,则d可简单图化当且仅当d’={d2-1,d3-1,……d(d1+1)-1, d(d1+2),d(d1+3),……dn}可简单图化。简单的说,把d排序后,找出度最大的点(设度为d1),把它与度次大的d1个点之间连边,然后这个点就可以不管了,一直继续这个过程,直到建出完整的图,或出现负度等明显不合理的情况。

注意:

1.图的总度是偶数。

2.每个点的度不超过N-1。

3.非下降排序,依次删边。若出现负度就是不合法的



AC代码:


#include<stdio.h>
#include<algorithm>
using namespace std;
bool cmp(int a,int b)
{
    return a>b;
}
int main()
{
    int t,n,i,j;
    int a[1010],flag;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(i=0; i<n; i++)
            scanf("%d",&a[i]);
        for(i=0; i<n; i++)
        {
            if(a[i]>n)
                break;
        }
        if(i<n)
        {
            printf("no\n");
            continue;
        }
        for(i=0; i<n; i++)
        {
            int cnt=0;
            flag=0;
            sort(a,a+n,cmp);
            for(j=1; j<n; j++)
            {
                if(cnt==a[0])
                    break;
                a[j]--;
                if(a[j]<0)
                {
                    flag=1;
                    break;
                }
                cnt++;
            }
            if(cnt==0)
                break;
            if(flag)
                break;
            a[0]-=cnt;
        }
        if(flag)
        {
            printf("no\n");
            continue;
        }
        for(i=0; i<n; i++)
        {
            if(a[i])
                break;
        }
        if(i<n)
            printf("no\n");
        else
            printf("yes\n");

    }
    return 0;
}

/*
4
4 3 2 1 1
*/


HDU 2454 Degree Sequence of Graph G (可简单图化的判定 havel定理)