/**
欧拉道路
1>.有向图忽略方向得到的无向图 是不是连通
2>.所有点的入度等于出度 或者 只有两个点的入度不等于出度,且一个入度比出度大一,另一个入度比出度小一
*/
#include
//// 并查集
求解是不是连通图
#include
#include
using namespace std; int r[30]; int find_(int x) { while(x!=r[x]) x=r[x]; return x; } int main() { int T,n,x,y,i,ok; char a[1005]; int in[30],out[30]; scanf("%d",&T); while(T--){ scanf("%d",&n); memset(r,-1,sizeof(r) ); memset(in,0,sizeof(in) ); memset(out,0,sizeof(out) ); while(n--){ scanf("%s",a); int m=strlen(a); int p=a[0]-'a',q=a[m-1]-'a'; in[p]++; out[q]++; if(r[p]==-1) r[p]=p; if(r[q]==-1) r[q]=q; x=find_(p); y=find_(q); if(x!=y) r[x]=y; } int jud=0; for(i=0;i<26;i++) /// 并查集判断 有向图忽略方向得到的无向图 是不是连通 if(r[i]==i) jud++; if(jud==1) ok=1; else ok=0; if(ok){ int m[30],ans=0; for(i=0;i<26;i++){ if(in[i]!=out[i]){ /// 入度不等于回路 ans++; m[ans]=i; } } if(!ans) ok=1; /// 所有点的入度等于出度 else if(ans==2){ /// 只有两个点的入度不等于出度 且 一个入度比出度大一 另一个入度比出度小一 if(in[m[1]]-out[m[1]]==1 && in[m[2]]-out[m[2]]==-1) ok=1; else if(in[m[1]]-out[m[1]]==-1 && in[m[2]]-out[m[2]]==1) ok=1; else ok=0; } else ok=0; } if(ok) printf("Ordering is possible.\n"); else printf("The door cannot be opened.\n"); } return 0; }
#include
//// dfs求解是不是连通图
#include
#include
using namespace std; int r[30][30],v[30]; void euler(int u) { v[u]=1; for(int i=0;i<26;i++){ if(r[u][i]&&v[i]==0) { euler(i); ///printf("%d[]\n",i); } } } int main() { int T,n,x,y,i,ok,j; char a[1005]; int in[30],out[30]; scanf("%d",&T); while(T--){ scanf("%d",&n); memset(r,0,sizeof(r) ); memset(in,0,sizeof(in) ); memset(out,0,sizeof(out) ); memset(v,-1,sizeof(v) ); while(n--){ scanf("%s",a); int m=strlen(a); int p=a[0]-'a',q=a[m-1]-'a'; in[p]++; out[q]++; v[p]=v[q]=0; ///if(p!=q) r[p][q]=r[q][p]=1; } int jud=0; for(i=0;i<26;i++){ /// 有向图忽略方向得到的无向图 是不是连通 dfs求解 for(j=0;j<26;j++){ if(r[i][j]){ euler(i); jud=1; break; } } if(jud) break; } ok=1; for(i=0;i<26;i++) if(v[i]==1||v[i]==-1) continue; else{ ok=0; break; } if(ok){ int m[30],ans=0; for(i=0;i<26;i++){ if(in[i]!=out[i]){ /// 入度不等于回路 ans++; m[ans]=i; } } if(!ans) ok=1; /// 所有点的入度等于出度 else if(ans==2){ /// 只有两个点的入度不等于出度 且 一个入度比出度大一 另一个入度比出度小一 if(in[m[1]]-out[m[1]]==1 && in[m[2]]-out[m[2]]==-1) ok=1; else if(in[m[1]]-out[m[1]]==-1 && in[m[2]]-out[m[2]]==1) ok=1; else ok=0; } else ok=0; } if(ok) printf("Ordering is possible.\n"); else printf("The door cannot be opened.\n"); } return 0; }