poj 2337 Catenyms 求有向图的字典序最小欧拉环路

缘起

【1】给出了有向图欧拉回路的判定算法. 【2】给出了无向图的欧拉环路的fleury算法. 所以要学习一下有向图的欧拉环路的求法. poj 2337 Catenyms

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
给你一些单词，如果一个单词的末尾字符与另一个单词首字符相同，则两个的单词可以连接。问是否可以把所有单词连
接起来，并且每个单词只能恰好用一次。 如果可以, 输出字典序最小解. 如果不能,输出 "***"

【输入】
多样例. 第一行是样例数t. 每个样例开始于一个n（3 <= n <= 1000），表示单词数量.
然后n行分别就是n个单词（都是小写英文字母）. 长度在[1,20]

【输出】
字典序最小的单词, 如果办不到, 输出 ***

【样例输入】
2
6
aloha
arachnid
dog
gopher
rat
tiger
3
oak
maple
elm

【样例输出】
aloha.arachnid.dog.gopher.rat.tiger
***

【限制】
1s

其实和【2】差不多——fleury算法完全可以运行于有向图. 本题的算法是显然的

  1. 通过并查集判断是否有根图
  2. 出入度判定是否存在欧拉路径, 不存在输出 ***
  3. 跑fleury算法. 输出字典序最小解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
//#include "stdafx.h"
#include <vector>
#include <algorithm>
using namespace std;
#include <stdio.h>
#include <string.h>
//#define LOCAL

int n, indeg[30], outdeg[30], f[30],start,ans[1005],top; // start是欧拉路径的出发点,ans是欧拉路径,top是ans中边的数量
bool v[1005], used[30];
char c[1005][25];
typedef pair<int,int> P; // first是顶点, second是边的编号(即单词编号)
vector<P> g[30];
typedef vector<P>::iterator vit;

bool cmp(P &a, P &b)
{
	return !~strcmp(c[a.second], c[b.second]); // 按照字典序升序排序每个点的出弧
}

int getf(int i)
{
	return f[i]==i?i:f[i]=getf(f[i]);
}

void merge(int i, int j) // 弧i->j 导致的并查集合并
{
	int fi = getf(i), fj = getf(j);
	if (fi==fj)
	{
		return;
	}
	f[fj] = fi;
}

bool ck()
{
	int p=0,q=0, pi, qi,sum=0; // pi记录欧拉路径的出发点,qi记录终点
	for (int i = 1; i<=26;i++)
	{
		if (used[i]&&f[i]==i)
		{
			sum++;
		}
	}
	if (sum>1) // 如果无根
	{
		return false;
	}
	for (int i = 26; i; i--) // 逆序是为了start=i这行代码
	{
		if (used[i])
		{
			start = i; // 如果最后存在欧拉回路的话, start保存的就是最小的字母, 它作为出发点(因为要输出字典序最小的解)
			if (indeg[i]==outdeg[i])
			{
				continue;
			}
			if (indeg[i]<outdeg[i])
			{
				p++;
				if (p>1)
				{
					return false;
				}
				pi = i;
			}
			else
			{
				q++;
				if (q>1)
				{
					return false;
				}
				qi = i;
			}
		}
	}
	if (p&&q)
	{
		start = pi;
		return outdeg[pi]-indeg[pi]==1 && outdeg[qi]-indeg[qi]==-1;
	}
	return !p&&!q;
}

void dfs(int i) // fleury算法
{
	for (vit x = g[i].begin(); x!=g[i].end();x++)
	{
		if (!v[x->second])
		{
			v[x->second] = true;
			dfs(x->first);
			ans[top++] = x->second;
		}
	}
}

int main()
{	
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	int kase;
	scanf("%d", &kase);
	while(kase--)
	{
		for (int i = 1; i<=26; i++)
		{
			f[i] = i;
		}
		memset(used, 0, sizeof(used));
		memset(indeg, 0, sizeof(indeg));
		memset(outdeg, 0, sizeof(outdeg));
		scanf("%d", &n);
		getchar();
		for (int i = 1; i<=26; i++)
		{
			g[i].clear();
		}
		for (int i = 1; i<=n;i++)
		{
			gets(c[i]);
			int len = strlen(c[i]);
			used[c[i][0]-'a'+1] = used[c[i][len-1]-'a'+1] = true;
			merge(c[i][0]-'a'+1, c[i][len-1]-'a'+1);
			indeg[c[i][len-1]-'a'+1]++;
			outdeg[c[i][0]-'a'+1]++;
			g[c[i][0]-'a'+1].push_back(P(c[i][len-1]-'a'+1, i)); // c[i][0] 这个字母通过 c[i]这个单词（弧）通往了 c[i][len-1]这个字母
		}
		if (!ck())
		{
			puts("***");
			continue;
		}
		top = 0; // 开始跑fleury算法输出字典序最小欧拉路径
		for (int i = 1; i<=26; i++)
		{
			sort(g[i].begin(), g[i].end(), cmp);
		}
		memset(v, 0, sizeof(v));
		dfs(start);
		// 输出字典序最小解
		for (int i = top-1; ~i;i--) // 逆序跑ans
		{
			printf("%s",c[ans[i]]);
			if (i)
			{
				putchar('.');
			}
		}
		puts("");
	}
	return 0;
}

本题虽然知识点较多, 但是每个都比较简单, 打熟了, 敲的行云流水的~ 爽的一笔

ac情况

20839974 yfsyfs 2337 Accepted 164K 0MS C++ 2579B 2019-09-07 07:32:38

参考

【1】https://yfsyfs.github.io/2019/09/06/hdu-1116-Play-on-Words-%E6%9C%89%E5%90%91%E5%9B%BE%E6%AC%A7%E6%8B%89%E5%9B%9E%E8%B7%AF%E5%AD%98%E5%9C%A8%E4%B8%8E%E5%90%A6%E7%9A%84%E5%88%A4%E5%AE%9A/

【2】https://yfsyfs.github.io/2019/09/06/poj-1041-John-s-trip-%E6%97%A0%E5%90%91%E5%9B%BE%E6%B1%82%E6%AC%A7%E6%8B%89%E5%9B%9E%E8%B7%AF%E6%A8%A1%E6%9D%BF/