WA后四个点,不知道哪错了
  • 板块P1127 词链
  • 楼主mieeee
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/4/17 11:40
  • 上次更新2024/4/17 16:36:24
查看原帖
WA后四个点,不知道哪错了
325983
mieeee楼主2024/4/17 11:40
#include<bits/stdc++.h>
using namespace std;
int n,head=-1,tail=-1;
struct Word{
	string s;
	int b,e;
}word[1005];
vector<int> oute[26],ine[26];
bool used[1005];
bool cmp(Word a,Word b){
	return a.s<b.s;
}

//并查集检查是否连通
int fa[26];
void init(){
	for(int i=0;i<26;i++){
		fa[i]=i;
	}
}
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
void merge(int i,int j){
	int x=find(i),y=find(j);
	fa[y]=x;
}
bool check_connected(){
	init();
	for(int i=1;i<=n;i++){
		if(used[i]==0){
			merge(word[i].b,word[i].e);
		}
	}
	int cnt=0;
	for(int i=0;i<26;i++){
		bool flag=0;
		for(int j:oute[i]){
			if(used[j]==0)flag=1;
		}
		for(int j:ine[i]){
			if(used[j]==0)flag=1;
		}
		if(flag==1){
			if(fa[i]==i)cnt++;
		}
	}
	if(cnt<=1)return 1;
	return 0;
}

//检查是否为半欧拉图
bool check_Eular(){
	if(!check_connected())return 0;
	for(int i=0;i<26;i++){
		int no=oute[i].size();
		int ni=ine[i].size();
		if(no==ni){
			continue;
		}
		if(no==ni+1){
			if(head==-1){
				head=i;
				continue;
			}
		}
		if(ni==no+1){
			if(tail==-1){
				tail=i;
				continue;
			}
		}
		return 0;
	}
	if(head==-1){//为欧拉图,选出现的最小字母为起点
		for(int i=0;i<26;i++){
			if(!oute[i].empty()){
				head=tail=i;
				break;
			}
		}
	}
	return 1;
}

int main()
{
	cin>>n;
	init();
	for(int i=1;i<=n;i++){
		string s;
		cin>>s;
		int len=s.length();
		int h=s[0]-'a';
		int t=s[len-1]-'a';
		word[i]={s,h,t};
	}
	sort(word+1,word+1+n,cmp);
	for(int i=1;i<=n;i++){
		oute[word[i].b].push_back(i);
		ine[word[i].e].push_back(i);
	}
	if(!check_Eular()){
		cout<<"***"<<endl;
		return 0;
	}
	//已知为半欧拉图,找一条欧拉通路
	int temp=head;
	for(int i:oute[temp]){
		if(used[i]==1)continue;
		used[i]=1;
		if(check_connected()){
			cout<<word[i].s;
			temp=word[i].e;
			break;
		}else{
			used[i]=0;
		}
	}
	while(true){
		bool flag=0;
		for(int i:oute[temp]){
			if(used[i]==1)continue;
			flag=1;
			used[i]=1;
			if(check_connected()){
				cout<<'.'<<word[i].s;
				temp=word[i].e;
				break;
			}else{
				used[i]=0;
			}
		}
		if(flag==0)break;
	}
	cout<<endl;
	return 0;
}
2024/4/17 11:40
加载中...