基本建图套路,从单词头向单词尾连一条边,答案就是是否存在一条欧拉路径
#include<bits/stdc++.h> using namespace std; const int N=2e5+10; int p[N]; int din[N],dout[N]; int st[N]; int find(int x){ if(x!=p[x]){ p[x]=find(p[x]); } return p[x]; } int g[50][50]; int main(){ int n,t; cin>>t; while(t--){ int n; cin>>n; int i; memset(st,0,sizeof st); memset(din,0,sizeof din); memset(dout,0,sizeof dout); for(i=0;i<=n;i++){ p[i]=i; } for(i=1;i<=n;i++){ string s; cin>>s; int a=s[0]-‘a‘,b=s[(int)s.size()-1]-‘a‘; st[a]=st[b]=1; g[a][b]++; dout[a]++,din[b]++; int pa=find(a),pb=find(b); p[pa]=pb; } int sign=-1; int res=0; for(i=0;i<26;i++){ if(st[i]){ if(sign==-1) sign=find(i); else{ if(sign!=find(i)){ res=1; break; } } } } int start=0,ed=0; for(i=0;i<26;i++){ if(din[i]!=dout[i]){ if(dout[i]==din[i]+1) start++; else if(din[i]-1==dout[i]) ed++; else{ res=1; break; } } } if(start!=0||ed!=0){ if(start!=1||ed!=1) res=1; } if(res==1){ cout<<"The door cannot be opened."<<endl; } else{ cout<<"Ordering is possible."<<endl; } } }