1185. 单词游戏

2023-12-14 09:53:57

题目链接

1185. 单词游戏
10106. 「一本通 3.7 例 2」单词游戏

有 \(N\) 个盘子，每个盘子上写着一个仅由小写字母组成的英文单词。

你需要给这些盘子安排一个合适的顺序，使得相邻两个盘子中，前一个盘子上单词的末字母等于后一个盘子上单词的首字母。

请你编写一个程序，判断是否能达到这一要求。

输入格式

第一行包含整数 \(T\)，表示共有 \(T\) 组测试数据。

每组数据第一行包含整数 \(N\)，表示盘子数量。

接下来 \(N\) 行，每行包含一个小写字母字符串，表示一个盘子上的单词。

一个单词可能出现多次。

输出格式

如果存在合法解，则输出”Ordering is possible.”，否则输出”The door cannot be opened.”。

数据范围

\(1≤N≤10^5\),
单词长度均不超过\(1000\)

输入样例：

3
2
acm
ibm
3
acm
malform
mouse
2
ok
ok

输出样例：

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

解题思路

欧拉路径

将单词的首末当作两个有边的结点，且由单词的首连向单词的尾，这样问题就转化为有向图中是否存在一条欧拉路径，其需要满足两个条件：

所有点的要么入度都等于出度即欧拉回路，要么只存在两个点不相等，且其中一个出度比入度多一（起点），另一个入度比出度多一（终点）
所有边连通

其中第一点比较好判断，关键在于第二点，这里稍有不同，题目要求所有的点连通，即不允许独立点的存在，可以用并查集判断所有点是否连通

时间复杂度：\(O(t\times n)\)

代码

// Problem: 单词游戏
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/1187/
// Memory Limit: 64 MB
// Time Limit: 1000 ms

// %%%Skyqwq
#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=30;
int t,n;
string s[100005];
int din[N],dout[N],fa[N];;
bool st[N];
int get(int x)
{
	if(x==fa[x])return x;
	return fa[x]=get(fa[x]);
}
int main()
{
	for(cin>>t;t;t--)
	{
		int cnt=0;
		memset(din,0,sizeof din);
		memset(dout,0,sizeof dout);
		memset(st,0,sizeof st);
		for(int i=0;i<26;i++)fa[i]=i;
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			cin>>s[i];
			int a=s[i][0]-'a',b=s[i].back()-'a';
			dout[a]++;
			din[b]++;
			st[a]=st[b]=true;
			fa[get(a)]=get(b);
		}
		bool success=true;
		int be=0,en=0;
		for(int i=0;i<26;i++)
			if(din[i]!=dout[i])
			{
				if(din[i]+1==dout[i])
					be++;
				else if(din[i]==dout[i]+1)en++;
				else
					success=false;
			}
		if((be||en)&&!(be==1&&en==1))success=false;
		int p=-1;
		for(int i=0;i<26;i++)
			if(st[i])
			{
				if(p==-1)p=get(i);
				else if(p!=get(i))success=false;
			}
		puts(success?"Ordering is possible.":"The door cannot be opened.");	
	}
	return 0;
}

码农公寓