首页 > 代码库 > poj1386欧拉回路的判定
poj1386欧拉回路的判定
#include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>#include <cmath>#include <stack>#include <queue>#include <vector>#include <map>#include <string>#include <iostream>using namespace std;int father[1000];int getfather(int x){ if(x!=father[x]) father[x]=getfather(father[x]); return father[x];}void add(int a,int b){ int fa=getfather(a);int fb=getfather(b); if(fa!=fb) father[fa]=fb;}int vis[111111];int out[100],in[1000];bool ok(){ int one=0;int two=0; int sum=0; for(int i=0;i<26;i++) if(vis[i]) if(father[i]==i) sum++; if(sum>1) return false; for(int i=0;i<26;i++){ if(in[i]-out[i]==1) one++; if(out[i]-in[i]==1) two++; if(out[i]==in[i]) continue; if(out[i]-in[i]>1||in[i]-out[i]>1) return false; } return ((one==1&&two==1)||(one==0&&two==0));// return one <= 1 && two <= 1}int main(){ int Icase;int n; int G[100][100]; char str[2000]; cin>>Icase; while(Icase--){ for(int i=0;i<26;i++) father[i]=i; cin>>n;int ans=0; memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); memset(G,0,sizeof(G)); memset(vis,0,sizeof(vis)); for(int i=0;i<n;i++){ scanf("%s",str);int a=str[0]-‘a‘;int len=strlen(str);int b=str[len-1]-‘a‘; add(a,b);in[b]++;out[a]++;vis[a]=1;vis[b]=1; } if(ok()) cout<<"Ordering is possible."<<endl; else cout<<"The door cannot be opened."<<endl; } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。