# 90分求助
  • 板块P1127 词链
  • 楼主yjm2007
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/9/29 22:36
  • 上次更新2023/10/27 09:30:04
查看原帖
# 90分求助
774362
yjm2007楼主2022/9/29 22:36
#include<bits/stdc++.h>
using namespace std;
vector<int> g[1002];
bool vis[1002];
int len[1002],chu[1002],ru[1002],po[200],qo[200],in[200];
int del[1002];
string a[1001];
int ans[1001],l=0;
int str(int x,int y)
{
  int ll=min(len[x],len[y]);
  for(int i=1;i<=ll;i++)
    {
      if(a[x][i-1]>a[y][i-1]) return 1;
      if(a[x][i-1]<a[y][i-1]) return -1;
    }
  if(len[x]==ll) return -1;
  else return 1;
}
void dfs(int x)
{
  for(int i=del[x];i<g[x].size();i=del[x])
    {
      del[x]++;
      if(vis[g[x][i]]==1)
        {
          vis[g[x][i]]=0;
          dfs(g[x][i]);
        }
    }
  ans[++l]=x;
}
int main()
{
  int n;
  cin>>n;
  for(int i=1;i<=n;i++)
    {
      cin>>a[i];
      vis[i]=1;
    }
  sort(a+1,a+1+n);
  for(int i=1;i<=n;i++)
    {
      len[i]=a[i].length();
    }
  for(int i=1;i<=n;i++)
    {
      for(int j=1;j<=n;j++)
        {
          if(j==i) continue;
          if(a[i][len[i]-1]==a[j][0])
            {
              g[i].push_back(j);
            }
        }
    }
  for(int i=1;i<=n;i++)
    {
      po[a[i][0]]++;
      qo[a[i][len[i]-1]]++;
    }
  int s=1,tot=0;
  for(int i=1;i<=n;i++)
    {
      if(po[a[i][0]]==qo[a[i][0]]+1&&in[a[i][0]]==0)
        {
          in[a[i][0]]=1;
          tot++;
          l=0;
          s=i;
        }
      if(tot>=2)
        {
          cout<<"***"<<endl;
          return 0;
        }
    }
  for(int i=1;i<=n;i++)
    {
      if(i==s||a[i][0]!=a[s][0]) continue;
      if(str(i,s)<0) s=i;
    }
  vis[s]=0;
  dfs(s);
  if(l==n)
            {
              for(int i=l;i>=1;i--)
    {
      if(i!=1)
        {
          cout<<a[ans[i]]<<".";
        }
      else
        {
          cout<<a[ans[i]]<<endl;
        }
    }
              return 0;
            }
  cout<<"***"<<endl;
  return 0;
}
2022/9/29 22:36
加载中...