一个有向图存在欧拉路:
在有向图中,如果图是弱连通的,并且图中除开两个顶点,其他所有顶点的入度等于出度,并且这两个点中,一个点入度比出度多1,另一个点出度比入度少1,那么该图存在欧拉路,这是个充要条件。
这个题中还要判断是是否连通,用并查集 记录判断下即可。
#include<cstdio> #include<iostream> #include<cstring> using namespace std; int in[50],out[50]; int root[50]; void init() { for(int i=0;i<=25;i++){ root[i]=i; } } int find(int x) { int temp=root[x]; if(x==root[x]) return x; else{ return root[x]=find(root[x]); } } int main() { int t; scanf("%d",&t); while(t--){ int n,i; init(); memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); char s[2000]; scanf("%d",&n); getchar(); for(i=0;i<n;i++){ gets(s); int l1=strlen(s); in[s[0]-‘a‘]++; out[s[l1-1]-‘a‘]++; int ra=find(s[0]-‘a‘); int rb=find(s[l1-1]-‘a‘); if(ra!=rb) root[rb]=ra; } int flag1=0,flag2=0; int flag3=0,time=0; for(i=0;i<=25;i++){ if(in[i]||out[i]){ if(i==find(i)) time++; } if(in[i]-out[i]==1) { flag1++;continue; } if(in[i]-out[i]==-1){ flag2++;continue; } if(in[i]!=out[i]) { printf("The door cannot be opened.\n"); flag3=1; break; } } if(flag3==0){ if(time==1){ if(flag1==0&&flag2==0) printf("Ordering is possible.\n"); else if(flag1==1&&flag2==1) printf("Ordering is possible.\n"); else printf("The door cannot be opened.\n"); } else printf("The door cannot be opened.\n"); } } }