题解

题目描述

原题来自：2009 Multi-University Training Contest 12 - Host by FZU
有 N N N个盘子，每个盘子上写着一个仅由小写字母组成的英文单词。你需要给这些盘子安排一个合适的顺序，使得相邻两个盘子中，前一个盘子上单词的末字母等于后一个盘子上单词的首字母。请你编写一个程序，判断是否能达到这一要求。如果能，请给出一个合适的顺序。

输入格式

多组数据。第一行给出数据组数 T T T ，每组数据第一行给出盘子数量 N N N，接下去 N N N 行给出小写字母字符串，一种字符串可能出现多次。

输出格式

若存在一组合法解输出Ordering is possible.，否则输出The door cannot be opened.。

样例

样例输入

3
2
acm
ibm
3
acm
malform
mouse
2
ok
ok

样例输出

The door cannot be opened.
Ordering is possible.
The door cannot be opened.

数据范围与提示

1 ≤ 1 0 5 , 0 ≤ M ≤ 2 × 1 0 5 ， 1 ≤ a , b ≤ N 1 \le 10^5,0 \le M \le 2 \times 10^5，1 \le a,b \le N 1≤105,0≤M≤2×105，1≤a,b≤N

题解

首先这道题的题目就是求一个可以不重复，不遗漏地遍历每一个盘子，要求是前后两个盘子的尾、首字母要相同

根据刚才的描述，我们可以发现这和欧拉通路很像，于是初始思路就来了：

依次判断每一个盘子，若两个盘子满足要求，则在这两个盘子间连一条边，最后判一下有没有欧拉通路就OK了。

但是这种思路有一些问题，因为我们像上面这么做，就相当于要求每两个盘子间的边都要遍历到（欧拉通路的定义嘛），然鹅题目只要求遍历完每个盘子就行了，所以我们就想到可不可以将盘子转化成边再判通路

我们这样想：盘子连接的条件就是首尾字母相同嘛，如果把盘子搞成了一条边，那么对于这条边，我们肯定需要且只需知道这个盘子的首位即可，于是把首尾设成边的起始和结尾即可，那么还有一个问题，这么建边后因该怎么判断两盘子可以相连，这不很简单吗，边的结尾连接另一条边的开始的条件就为这两个字母相等就好了，因为共有26个字母，所以我们最多只需要26个节点就好了

比如样例的第二组：

3
acm
malform
mouse

我们画出来的图就是这样的（边上的单词只是为了理解方便，实际实现时不用存），显然存在欧拉通路

我们再来一个不行的案例：

3
tan
tai
nb

在这张图中就不存在欧拉回路，所以答案也肯定是无解的，事实上，读者也可以自行枚举一下，确实是不行的

有了这些，我们就可以写出代码，注意还要判断一下是否连通，不连通也是无解的

代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN=100005;
char a[MAXN];
int in[35];
int out[35];
int fa[35];
int find(int x){//查找爸爸(并查集基本操作) 
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
void mer(int u,int v){//合并(并查集基本操作) 
	int fu=find(u);
	int fv=find(v);
	if(fu!=fv){
		fa[fu]=fv;
	}
}
int main(){
	int t;
	scanf("%d",&t);
	int n;
	while(t--){
		scanf("%d",&n);
		memset(in,0,sizeof(in));
		memset(out,0,sizeof(out));
		for(int i=1;i<=26;i++){//并查集初始化 
			fa[i]=i;
		}
		for(int i=1;i<=n;i++){
			scanf("%s",a+1); 
			int u=a[1]-'a'+1;
			int len=strlen(a+1);
			int v=a[len]-'a'+1;
			in[v]++;//统计入度 
			out[u]++;//统计出度 
			mer(v,u);
		}
		int fath=-1;
		int cnt=0; 
		for(int i=1;i<=26;i++){//判连通 
			if(((in[i] || out[i]) && find(i)==i) || abs(in[i]-out[i])>1){ 
				cnt++;
			}
		}
		if(cnt>1){
			printf("The door cannot be opened.\n");
			continue;
		}
		int cnti=0,cnto=0;
		for(int i=1;i<=26;i++){//欧拉通路板子 
			if(in[i]-out[i]==1){
				cnti++;
			}
			if(in[i]-out[i]==1){
				cnto++;
			}
		}
		if(cnti==cnto==1){
			printf("Ordering is possible.\n");
		}
		else{
			printf("The door cannot be opened.\n");
		}
	}
return 0;
}