题意：判断一些单词能不能首尾连成一体
#include <iostream> #include <algorithm> #include <cstring> #include <cmath> #include <cstdio> using namespace std; int n,father[30],range[30],save[100010],in[30],out[30]; bool use[30]; char s[1010]; void add(int x) {use[x]=true;father[x]=x;range[x]=0; } int Find(int x) {int k=0;while(x!=father[x]){save[k++]=x;x=father[x];}for(int j=0; j<k; j++)father[save[j]]=x;return x; } void uni(int x,int y) {int a=Find(x),b=Find(y);if(a!=b){if(range[a]<range[b]) father[a]=b;else{father[b]=a;if(range[a]==range[b]) range[a]++;}} } int main() {freopen("in.txt","r",stdin);int t;scanf("%d",&t);while(t--){scanf("%d",&n);memset(use,false,sizeof(use));memset(father,0,sizeof(father));memset(range,0,sizeof(range));memset(in,0,sizeof(in));memset(out,0,sizeof(out));for(int i=1; i<=n; i++){scanf("%s",s);int l=strlen(s),x=s[0]-'a',y=s[l-1]-'a';if(use[x]==false) add(x);if(use[y]==false) add(y);in[x]++;out[y]++;uni(x,y);}int flag=0;for(int i=0; i<26; i++){if(use[i]==true&&Find(i)==i){flag++;}}if(flag>1) printf("The door cannot be opened.\n");else{int a=0,b=0,i;for(i=0;i<26;i++){if(use[i]&&in[i]!=out[i]){if(in[i]-out[i]==1) a++;else if(out[i]-in[i]==1) b++;else break;}}if(i<26) printf("The door cannot be opened.\n");else if(a+b==0||a==1&&b==1) printf("Ordering is possible.\n");else printf("The door cannot be opened.\n");}}return 0; }
