18pts 求助 感觉思路死对
  • 板块P1127 词链
  • 楼主dfydn
  • 当前回复0
  • 已保存回复0
  • 发布时间2021/9/23 20:39
  • 上次更新2023/11/4 05:49:38
查看原帖
18pts 求助 感觉思路死对
112048
dfydn楼主2021/9/23 20:39
#include<cstdio>
#include<iostream> 
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100005;
int head[N];
int x;
int tot;
int deg[N],ji;
bool g[1005][1005];
bool vis[N];
bool flag;
int n;
struct node{
	int to,next;
}edge[N<<1];
string s[N];
void add(int u,int v){
	edge[tot].to=v;
	edge[tot].next=head[u];
	head[u]=tot++;
}
void dfs(int u){
	vis[u]=1;
	if(deg[u]%2) ji++;
	for(int i=head[u];i!=-1;i=edge[i].next){
		int v=edge[i].to;
		if(vis[v]) continue;
		dfs(v);
	}
}
void dfs2(int u){
	vis[u]=1;
	int toto=100000005;
	if(!flag){
		cout<<s[u];
		flag=1;
	}
	else{
		cout<<"."<<s[u];
	}
	for(int i=head[u];i!=-1;i=edge[i].next){
		int v=edge[i].to;
		if(vis[v]) continue;
		if(v<toto&&s[v][0]==s[u][s[u].length()-1]) toto=v;
	}
	if(toto!=100000005) dfs2(toto);
}
bool cmp(string x,string y){
//	int lx=x.length(),ly=y.length(),minn;
//	minn=min(lx,ly);
//	for(int i=0;i<minn;i++){
//		if(x[i]<y[i]) return 1;
//		if(x[i]>y[i]) return 0;
//	}
//	return lx<ly;、
	return x<y; 
}
int main(){
	memset(head,-1,sizeof(head));
	scanf("%d",&n);
	for(int i=1;i<=n;i++) cin>>s[i];
	sort(s+1,s+n+1,cmp);
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			int l1=s[i].length(),l2=s[j].length();
			if(s[i][0]==s[j][l2-1]){
				if(g[i][j]) continue;
				g[i][j]=g[j][i]=1;
				add(i,j); add(j,i);
				deg[i]++; deg[j]++;
			}
			if(s[i][l1-1]==s[j][0]){
				if(g[i][j]) continue;
				g[i][j]=g[j][i]=1;
				add(i,j); add(j,i);
				deg[i]++; deg[j]++;
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			if(i==1){
				dfs(i);
				if(ji!=0&&ji!=2){
					printf("***");
					return 0;
				}
			}
			else{
				printf("***");
				return 0;
			}
		}
	}
	memset(vis,0,sizeof(vis));
	if(ji){
		for(int i=1;i<=n;i++){
			if(deg[i]%2){
				x=i;
				break;
			}
		}
		dfs2(x);
	}
	else{
		dfs2(1);
	}
	return 0;
}
2021/9/23 20:39
加载中...