首页 > 代码库 > ZOJ 3732 Graph Reconstruction Havel_Hakimi定理
ZOJ 3732 Graph Reconstruction Havel_Hakimi定理
链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5078
题意:有N个点组成无向图,每个点的度为ai,问是否能组成图,并且组成的图方式是否唯一。
思路:Havel_Hakimi定理的应用。
(以下转载)
1,Havel-Hakimi定理主要用来判定一个给定的序列是否是可图的。
2,首先介绍一下度序列:若把图 G 所有顶点的度数排成一个序列 S,则称 S 为图 G 的度序列。
3,一个非负整数组成的有限序列如果是某个无向图的序列,则称该序列是可图的。
4,判定过程:(1)对当前数列排序,使其呈递减,(2)从S【2】开始对其后S【1】个数字-1,(3)一直循环直到当前序列出现负数(即不是可图的情况)或者当前序列全为0 (可图)时退出。
5,举例:序列S:7,7,4,3,3,3,2,1 删除序列S的首项 7 ,对其后的7项每项减1,得到:6,3,2,2,2,1,0,继续删除序列的首项6,对其后的6项每项减1,得到:2,1,1,1,0,-1,到这一步出现了负数,因此该序列是不可图的。
(转载结束)
判断是否成图方式唯一的方法是在每个点寻找连接的边的时候,找到的最后一个点,如果与它之后第一个度不为零的点的度是相同的,则两个点可以交换位置并且不影响建图可能性,而出现至少两种建图方式。
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <map> #include <cstdlib> #include <queue> #include <stack> #include <vector> #include <ctype.h> #include <algorithm> #include <string> #include <set> #define PI acos(-1.0) #define maxn 10005 #define INF 0x7fffffff #define eps 1e-8 typedef long long LL; typedef unsigned long long ULL; using namespace std; struct aa { int num; int degree; } a[105],b[105]; int way[10005][2]; bool cmp1(aa a,aa b) { return a.degree>b.degree; } int main() { int tot; while(~scanf("%d",&tot)) { int top=0,A,B; bool flag1=0,flag2=0; for(int i=0; i<tot; i++) { a[i].num=b[i].num=i; scanf("%d",&a[i].degree); b[i].degree=a[i].degree; } for(int i=0; i<tot; i++) { sort(b+i,b+tot,cmp1); if(i+b[i].degree>=tot) { flag1=1; break; } int tt=0; for(int j=i+1; j<tot; j++) { if(!b[j].degree) continue; tt++; way[top][0]=b[i].num; way[top++][1]=b[j].num; if(tt==b[i].degree) { int p=j+1; while(b[p].degree==0&&p<tot) p++; if(p<tot&&b[p].degree==b[j].degree) flag2=1; } b[j].degree--; if(b[j].degree<0) { flag1=1; break; } if(tt==b[i].degree) break; } if(tt<b[i].degree) flag1=1; if(flag1==1) break; } if(!flag1&&!flag2) { printf("UNIQUE\n"); printf("%d %d\n",tot,top); for(int i=0; i<top; i++) { if(i==0) printf("%d",way[i][0]+1); else printf(" %d",way[i][0]+1); } printf("\n"); for(int i=0; i<top; i++) { if(i==0) printf("%d",way[i][1]+1); else printf(" %d",way[i][1]+1); } printf("\n"); } else if(flag1) printf("IMPOSSIBLE\n"); else { printf("MULTIPLE\n"); printf("%d %d\n",tot,top); for(int i=0; i<top; i++) { if(i==0) printf("%d",way[i][0]+1); else printf(" %d",way[i][0]+1); } printf("\n"); for(int i=0; i<top; i++) { if(i==0) printf("%d",way[i][1]+1); else printf(" %d",way[i][1]+1); } printf("\n"); printf("%d %d\n",tot,top); top=0; flag2=0; for(int i=0; i<tot; i++) b[i]=a[i]; for(int i=0; i<tot; i++) { sort(b+i,b+tot,cmp1); if(i+b[i].degree>=tot) { flag1=1; break; } int tt=0; for(int j=i+1; j<tot; j++) { if(!b[j].degree) continue; tt++; if(tt==b[i].degree&&flag2==0) { int p=j+1; while(b[p].degree==0&&p<tot) p++; if(p<tot&&b[p].degree==b[j].degree) { flag2=1; j=p; } } way[top][0]=b[i].num; way[top++][1]=b[j].num; b[j].degree--; if(tt==b[i].degree) break; } } for(int i=0; i<top; i++) { if(i==0) printf("%d",way[i][0]+1); else printf(" %d",way[i][0]+1); } printf("\n"); for(int i=0; i<top; i++) { if(i==0) printf("%d",way[i][1]+1); else printf(" %d",way[i][1]+1); } printf("\n"); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。