36分求调
  • 板块P1127 词链
  • 楼主n_bluetea
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/5/10 09:47
  • 上次更新2024/5/10 15:45:30
查看原帖
36分求调
588080
n_bluetea楼主2024/5/10 09:47
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5;

int in[maxn];
int ou[maxn];
int fa[maxn];
int letter[maxn];
string a[maxn];

struct edge
{
	int to, next;
	string w;
}e[maxn];
int head[maxn];
int n, set_count, cnt = 1;

int cmp(string a, string b)
{
	return a > b;
}

void add(int a, int b, string c)
{
	e[cnt].to = b;
	e[cnt].w = c;
	e[cnt].next = head[a];
	head[a] = cnt++;
}

void terminates()
{
	cout << "***\n";
	exit(0);
}

int find(int x)
{
	if (fa[x] == x) return x;
	return fa[x] = find(fa[x]);
}

void unions(int a, int b)
{
	fa[find(a)] = find(b);
}

int vis[maxn];
vector<string> ans;
void dfs(int st, int now)//st:点个数,now:当前点,pre_edge:前一条边
{
	if (st == n)
	{
		for (int i = 0; i < ans.size(); i++)
		{
			cout << ans[i];
			if (i != ans.size() - 1)cout << ".";
		}
		exit(0);
	}

	for (int i = head[now]; i; i = e[i].next)//遍历以now为起点的边
	{
		
		if (vis[i]) continue;

		vis[i] = 1;
		ans.push_back(e[i].w);
		dfs(st + 1, e[i].to);
		vis[i] = 0;
	} 
}

int main()
{
	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	sort(a + 1, a + n + 1, cmp);

	//构建一个以字母为顶点,单词为边的有向图
	for (int i = 1; i <= n; i++)
	{
		int ch_start = a[i][0] - 'a' + 1;		      //起点
		int ch_end = a[i][a[i].size() - 1] - 'a' + 1; //终点

		in[ch_end]++;
		ou[ch_start]++;
		add(ch_start, ch_end, a[i]);

		//起点没有出现过
		if (!letter[ch_start])
		{
			set_count++;
			letter[ch_start] = 1;
			fa[ch_start] = ch_start;
		}

		//终点没有出现过
		if (!letter[ch_end])
		{
			set_count++;
			letter[ch_end] = 1;
			fa[ch_end] = ch_end;
		}

		//如果不是自环,将该边放入集合
		if (ch_start != ch_end)
		{
			int stf = find(ch_start);
			int edf = find(ch_end);

			if (stf != edf)//如果不是同一集合,则合并
			{
				set_count--;
				unions(stf, edf);
			}
		}
	}

	//判断图是否是欧拉图

	//条件一:如果具有多个连通块,那么不是欧拉图
	if (set_count != 1)
	{
		terminates();
	}

	//条件二:对于有向图,除了起点和终点,入度和出度相同,起点出度比入度多1,终点入度比出度多1
	//条件三:只有一个起点和终点或者没有起点或终点
	int eular_start = 0;
	int eular_end   = 0;
	for (int i = 1; i <= 27; i++)
	{
		if (!letter[i])
			continue;

		int f1 = 0;
		if (ou[i]==in[i]+1)//起点
		{
			if (f1 == 1)
				terminates();
			f1 = 1;
			eular_start = i;
			continue;
		}

		int f2 = 0;
		if (in[i] == ou[i] + 1)//终点
		{
			if (f2 == 1)
				terminates();
			f2 = 1;
			eular_end = i;
			continue;
		}

		if (in[i] == ou[i])
			continue;
		terminates();//如果一个点,既不是起点,也不是终点,同时不满足条件,那么该图不是欧拉图
	}
	
	if ((eular_start && !eular_end) || (!eular_start && eular_end))//有始无终/有终无始
	{
		terminates();
	}
	if (!eular_start)eular_start = a[1][0] - 'a' + 1;//没有起点就构造起点(回路)
		

	//寻找最短欧拉回路
	//因为每个点出边已经排好了序,所有如果两个点之间存在多条边,我们必然先选择字典序小的边,所以顺序遍历即可。在搜索时顺便记录答案
	dfs(0, eular_start);	
	return 0;
}
2024/5/10 09:47
加载中...