91pts,WA on #2 ,求调,谢谢QwQ
  • 板块P1127 词链
  • 楼主SpreadWings
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/11/8 17:39
  • 上次更新2023/10/28 21:11:15
查看原帖
91pts,WA on #2 ,求调,谢谢QwQ
655425
SpreadWings楼主2022/11/8 17:39
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
struct Edge{
	int to;
	int next;
	string w;
}g[N];
int head[27],cnt;
void addEdge(int from,int to,string w){
	cnt++;
	g[cnt].to=to;
	g[cnt].next=head[from];
	g[cnt].w=w;
	head[from]=cnt;
	return ;
}
int n;
string s[N];
int in[27],out[27];
int fa[27];
bool exist[27];
int find(int x){
	if(fa[x]==0)fa[x]=x;
	if(fa[x]==x)return x;
	fa[x]=find(fa[x]);
	return fa[x];
}
void merge(int x,int y){
	x=find(x);y=find(y);
	fa[x]=y;return ;
}
int check(){
	int tmp=0;
	for(int i=2;i<=26;i++){
		if(exist[i]==0)continue;
		if(!tmp)tmp=find(i);
		else if(tmp!=find(i))return -1;
	}
	int ret;
	int c1,c2;
	c1=c2=0;
	for(int i=1;i<=26;i++){
		if(exist[i]==0)continue;
		if(in[i]==out[i])continue;
		if(in[i]+1==out[i]){
			ret=i;c1++;
		}else if(in[i]==out[i]+1){
			c2++;
		}else{
			return -1;
		}
	}
	if(c1==1&&c2==1)return ret;
	else if(c1==0&&c2==0)return 1;
	return -1;
}
string ans[N];
bool flag;
bool vis[N];
void dfs(int dep,int x){
	if(flag)return ;
	if(dep==cnt+1){
		flag=1; 
		return ;
	}
	for(int i=head[x],y;i;i=g[i].next){
		if(vis[i])continue;
		y=g[i].to;
		vis[i]=1;
		ans[dep]=g[i].w;
		dfs(dep+1,y);
		vis[i]=0;
		if(flag)return ;
	}
	return ;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)cin>>s[i];
	sort(s+1,s+1+n);
	//按字典序从小到大排序,然后逆序遍历建边,因为用的是链式前向星,所以会优先搜到字典序小的边 
	for(int i=n;i>=1;i--){
		addEdge(s[i][0]-'a'+1,s[i][s[i].length()-1]-'a'+1,s[i]);
		out[s[i][0]-'a'+1]++;
		in[s[i][s[i].length()-1]-'a'+1]++;
		merge(s[i][0]-'a'+1,s[i][s[i].length()-1]-'a'+1);
		exist[s[i][0]-'a'+1]=exist[s[i][s[i].length()-1]-'a'+1]=1;
	}
	int st=check();
	if(st==-1){
		printf("***");
	}else{
		dfs(1,st);
		if(flag){
			cout<<ans[1];
			for(int i=2;i<=cnt;i++){
				cout<<'.'<<ans[i];
			}
		}else{
			printf("***");
		}
	}
	return 0;
}
2022/11/8 17:39
加载中...