首页 > 代码库 > 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定理)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。