题目链接：
思路：
（1）将每个单词视为有向路径，单词的起始字母是起始节点，末尾字母是终止节点，然后找由字母建立的有向图
是否是欧拉图或者半欧拉图。
（2）先用并查集判断是否连通，再判断入度与出度的·关系是否符合要求。
#include#include #include #include #include using namespace std;const int maxn = 100100;int fa[120],in[120],out[120];string ss[maxn];struct Edge{ int to,next,id;}edge[maxn*2];int vis[maxn],head[maxn],tot;int f(int x){ if(fa[x]==0) return x; else return fa[x]=f(fa[x]);}void Init(){ memset(fa,0,sizeof(fa)); memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); memset(vis,0,sizeof(vis)); memset(head,0,sizeof(head)); tot=0;}void add(int x,int y,int w){ edge[tot].to=y; edge[tot].next=head[x]; edge[tot].id=w; head[x]=tot++;}int main(void){ //printf("%d\n",'z'-'a'+1); int N,i,n,j,x,y,t1,t2; scanf("%d",&N); while(N--){ scanf("%d",&n); Init(); for(i=1;i<=n;i++){ cin>>ss[i]; x=ss[i][0]-'a'+1; y=ss[i][ss[i].length()-1]-'a'+1; t1=f(x);t2=f(y); if(t1!=t2) fa[t2]=t1; in[y]++; out[x]++; add(x,y,i); } int fg=1; x=f(x); for(i=1;i<=n;i++){ y=ss[i][0]-'a'+1; if(f(y)!=x){ fg=0;break; } y==ss[i][ss[i].length()-1]-'a'+1; if(f(y)!=x){ fg=0;break; } } if(fg==1){ int tt=1,cc=0; for(i=1;i<=26;i++){ if(abs(in[i]-out[i])>1){ tt=0;break; } else if(abs(in[i]-out[i])==1){ cc+=(in[i]-out[i]); } } if(tt==1&&cc==0) printf("Ordering is possible.\n"); else printf("The door cannot be opened.\n"); } else printf("The door cannot be opened.\n"); } return 0;}