首页 > 代码库 > HDU - 1116 Play on Words
HDU - 1116 Play on Words
有向图是否具有欧拉通路或回路的判定:
欧拉通路:图连通;除2个端点外其余节点入度=出度;1个端点入度比出度大1;一个端点入度比出度小1 或 所有节点入度等于出度
欧拉回路:图连通;所有节点入度等于出度
#include<stdio.h>#include<string.h>#define MAX 27int in[MAX],out[MAX];int visit[MAX],father[MAX];int find(int index){ if(index==father[index]) return index; else return find(father[index]);}int main(void){ int t,n; int i,j; int s,e; char str[1001]; scanf("%d",&t); while(t--) { scanf("%d",&n); memset(visit,0,sizeof(visit)); memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); for(i=0;i<MAX;i++) father[i]=i; for(i=0;i<n;i++){ scanf("%s",str); int len=strlen(str); s=str[0]-‘a‘,e=str[len-1]-‘a‘; father[s]=father[e]=find(s); visit[s]=visit[e]=1; out[s]++;in[e]++; } //判断改图是否连通 int r=0; for(i=0;i<MAX;i++){ if(visit[i]&&i==father[i]) r++; } if(r>1){ //aba abc printf("The door cannot be opened.\n"); continue; } int x,y,z,h; x=y=z=h=0; for(i=0;i<MAX;i++){ if(visit[i]){ if(out[i]-in[i]==1==1) x++; else if(in[i]-out[i]==1)y++; else if(in[i]==out[i]) z++; else h++; } } if(h==0&&((x==1&&y==1)||(x==0||y==0))) printf("Ordering is possible.\n"); else printf("The door cannot be opened.\n"); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。