题解 UVA10129 【单词 Play on Words】
血色黄昏
·
·
题解
几乎是个模板题w
很容易能看出来这是道欧拉回路板子。回想我们小学学过的的一笔画问题，那是解决无向图的欧拉回路的，所以不能用在此题，关于有向图的欧拉回路定义如下：
$2.$除两个节点外，其它节点全部满足1。而这两个节点其中一个的入度比出度大1，另一个的出度比入度大1
是不是很好理解呢qwq
所以本题思路就出来了：连边只需要看头和尾。由于是一笔画，所以要先判断是否只有一个连通块，用道法术或者并查集都能轻松解决。如果符合就判断它的入度出度也是否符合欧拉回路即可，写起来很简单
注释都在代码里了，照着那两条规定判断即可
```cpp
#include<bits/stdc++.h>
using namespace std;
string l[1000010];
bool vis[27];//是否访问
int in[27], out[27], fa[27];//入度，出度，祖先
int find(int x) //并查集的查询操作
{
return fa[x] == x?x:find(fa[x]);
}
int main()
{
int t;
cin>>t;
while(t --) //T组数据
{
int n;
cin>>n;
memset(vis, false, sizeof(vis));
for(int i = 1; i <= 26;i ++) fa[i] = i;//并查集初始化
for(int i = 1; i <= n; i++)
{
cin>>l[i];
in[l[i][l[i].size() - 1] - 'a' + 1] ++;//入度+1
out[l[i][0] - 'a' + 1] ++;//出度+1
vis[l[i][l[i].size() - 1] - 'a' + 1] = vis[l[i][0] - 'a' + 1] = true;//标记为访问
int x = find(l[i][l[i].size() - 1] - 'a' + 1);//找祖宗
int y = find(l[i][0] - 'a' + 1);//找祖宗
if (x != y) fa[x] = y;//合并
}
int cnt = 0;//初始化为0
for (int i = 1; i <= 26;i ++)if(vis[i] and find(i) == i)cnt ++;//如果自己是祖先cnt+1
if (cnt > 1) //如果有多个连通块无解
{
puts("The door cannot be opened.");
continue;
}
vector<int>ll;
for (int i = 1;i <= 26;i ++)if(vis[i] and in[i] != out[i])ll.push_back(i);
if (ll.size() != 0 and ll.size() != 2) //如果大小不为0或2无解
{
cout<<"The door cannot be opened."<<endl;
}
else if (ll.empty())//空的显然有解
{
cout<<"Ordering is possible."<<endl;
}
else if (in[ll.front()] - out[ll.front()] == 1 and out[ll.back()] - in[ll.back()] == 1) //出入度差为一且只有一个有节
{
cout<<"Ordering is possible."<<endl;
}
else if (out[ll.front()] - in[ll.front()] == 1 and in[ll.back()] - out[ll.back()] == 1) //同上
{
cout<<"Ordering is possible."<<endl;
}
else cout<<"The door cannot be opened."<<endl;//不然则无解
}
return 0;
}
```
期末考前发题解rp++awa