64pts 大佬求调
  • 板块P1127 词链
  • 楼主2206GZ
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/11/14 19:11
  • 上次更新2023/11/14 20:40:05
查看原帖
64pts 大佬求调
948336
2206GZ楼主2023/11/14 19:11
#include<bits/stdc++.h>
using namespace std;
map <string,int> m;
vector <int> v[1005];
string k[1005];
int x[30],y[30],flag[1005],o=0,h[1005],n;
int dfs(int l)
{
	flag[l]=1;
	h[++o]=l;
	if(o==n)
	return 1;
	for(int i=0;i<v[l].size();i++)
	if(flag[v[l][i]]==0)
	{
		if(dfs(v[l][i])==1)
			return 1;
		else 
		{
			o--;
			flag[v[l][i]]=0;
		}
	}
	return 2;	
} 
int main()
{
	string s;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>s;
		k[i]=s;
		x[s[0]-96]++;
		y[s[s.size()-1]-96]++;
	}
	sort(k+1,k+n+1);
	for(int i=1;i<=n;i++)
	m[k[i]]=i;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		if(i!=j&&k[i][k[i].size()-1]==k[j][0])
		v[m[k[i]]].push_back(m[k[j]]);
	for(int i=1;i<=26;i++)
	{
		if(x[i]-y[i]==1)
		{
			for(int j=1;j<=n;j++)
			{
				if(k[j][0]-96==i)
				if(dfs(j)==1)
				{
					cout<<k[h[1]];
					for(int t=2;t<=n;t++)
					cout<<"."<<k[h[t]];
					return 0;
				}
				else 
				{
					o=0;
					memset(flag,0,sizeof(flag));
					memset(h,0,sizeof(h));
				}
			}
		}
	}
	for(int i=1;i<=n;i++)
	if(dfs(i)==1)
	{
		cout<<k[h[1]];
		for(int t=2;t<=n;t++)
		cout<<"."<<k[h[t]];
		return 0;
	}
	else 
	{
		o=0;
		memset(flag,0,sizeof(flag));
		memset(h,0,sizeof(h));
	}
	cout<<"***";
}
2023/11/14 19:11
加载中...