欧拉路 之 一本通1528：【例 2】单词游戏

题面

1528：【例 2】单词游戏
时间限制: 1000 ms 内存限制: 32768 KB
提交数: 324 通过数: 143
【题目描述】
来自 ICPC CERC 1999/2000，有改动。
有 N 个盘子，每个盘子上写着一个仅由小写字母组成的英文单词。你需要给这些盘子安排一个合适的顺序，使得相邻两个盘子中，前一个盘子上单词的末字母等于后一个盘子上单词的首字母。请你编写一个程序，判断是否能达到这一要求。如果能，请给出一个合适的顺序。
【输入】
多组数据。第一行给出数据组数 T，每组数据第一行给出盘子数量 N，接下去 N 行给出小写字母字符串，一种字符串可能出现多次。
【输出】
若存在一组合法解输出Orderingispossible.，否则输出Thedoorcannotbeopened.。
【输入样例】
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≤N≤105,∣S∣≤1000
一句话题意：求能不能把所有字符串首尾各一个字母相连，连成一串

思路

两点，首先是得连通，其次是需要能构成欧拉路
连通我用并查集做的，如下：
首先输入时有一句fa[find(x)]=find(y)（x是首字母，y是尾字母，连一条边）

for(int i=1; i<=26&&flag; i++) if(vis[i])
        if(ans==-1) ans=find(i);
        else if(ans!=find(i)) printf("The door cannot be opened.\n"),flag=0;

find函数如下：

int find(int k)
{
  if(k==fa[k]) return k;
  return fa[k]=find(fa[k]);
}

欧拉路求法如下：

for(int i=1; i<=n; i++)
      cin>>s,x=s[0]-96,y=s[s.length()-1]-96,fa[find(x)]=find(y),cnt[x]++,cntt[y]++,vis[x]=vis[y]=1;
    for(int i=1; i<=26&&flag; i++)
      if(cnt[i]!=cntt[i])
      {
        if(cnt[i]-cntt[i]==1&&!v1) v1=1;
        else if(cnt[i]-cntt[i]==-1&&!v2) v2=1;
        else printf("The door cannot be opened.\n"),flag=0;
      }

就是有向图求欧拉路。

代码

#include <bits/stdc++.h>
using namespace std;
int n,t,cnt[30],cntt[30],fa[30],ans,x,y;
string s;
bool flag,v1,v2,vis[30];
int find(int k)
{
  if(k==fa[k]) return k;
  return fa[k]=find(fa[k]);
}
int main()
{
  scanf("%d",&t);
  while(t--)
  {
    scanf("%d",&n),memset(cnt,0,sizeof(cnt)),memset(cntt,0,sizeof(cntt));
    flag=1,v1=0,v2=0,memset(vis,0,sizeof(vis)),ans=-1;
    for(int i=1; i<=26; i++) fa[i]=i;
    for(int i=1; i<=n; i++)
      cin>>s,x=s[0]-96,y=s[s.length()-1]-96,fa[find(x)]=find(y),cnt[x]++,cntt[y]++,vis[x]=vis[y]=1;
    for(int i=1; i<=26&&flag; i++)
      if(cnt[i]!=cntt[i])
      {
        if(cnt[i]-cntt[i]==1&&!v1) v1=1;
        else if(cnt[i]-cntt[i]==-1&&!v2) v2=1;
        else printf("The door cannot be opened.\n"),flag=0;
      }
    for(int i=1; i<=26&&flag; i++) if(vis[i])
        if(ans==-1) ans=find(i);
        else if(ans!=find(i)) printf("The door cannot be opened.\n"),flag=0;
    if(flag) printf("Ordering is possible.\n");
  }
  return 0;
}

小结

这题两点要判断，首先是得连通，其次是需要能构成欧拉路。
联通用并查集，欧拉路用入出度，即可
欢迎私信。

完结撒花！！！
别忘了点赞，关注，谢谢！！