Uva 10129 - Play on Words 单词接龙 欧拉道路应用
跟Uva 10054很像，不过这题的单词是不能反向的，所以是有向图，判断欧拉道路。
关于欧拉道路（from Titanium大神）：
判断有向图是否有欧拉路
1.判断有向图的基图（即有向图转化为无向图）连通性，用简单的DFS即可。如果图都不连通，一定不存在欧拉路
2.在条件1的基础上
对于欧拉回路，要求苛刻一点，所有点的入度都要等于出度，那么就存在欧拉回路了
对于欧拉道路，要求松一点，只有一个点，出度比入度大1，这个点一定是起点； 一个点，入度比出度大1，这个点一定是终点.其余点的出度等于入度
（注意，只能大1，而且这样的点分别只能有1个,而且存在起点就一定要存在终点，存在终点就一定要存在起点）
他用判断连通性用的是DFS，我用的是并查集实现。
然后判断为欧拉回路（入度=出度）或者欧拉道路（出入度相差1的点只有不同的两个）（而且其他点出度=入度！）。
代码：
#include <cstdio>
#include <cstdlib>
#include <cstring>
const int maxn = 30;
int f[maxn], g[maxn][maxn], id[maxn], od[maxn];
int t, n, root;
int Find(int x) {
if (x != f[x])
return f[x] = Find(f[x]);
return x;
}
int main () {
scanf("%d", &t);
while (t--) {
char word[1001];
scanf("%d", &n);
for (int i = 0; i < maxn; i++) {
f[i] = i;
id[i] = 0;
od[i] = 0;
for (int j = 0; j < maxn; j++)
g[i][j] = 0;
}
for (int i = 0; i < n; i++) {
scanf("%s", word);
int a = word[0] - 'a', b = word[strlen(word) - 1] - 'a';
g[a][b]++;
od[a]++;
id[b]++;
f[Find(a)] = Find(b);
root = Find(b);
}
int i, ans = 0, flag = 1, in = 0, on = 0;
for (i = 0; i < maxn; i++)
if (id[i] || od[i]) {
if (Find(f[i]) != root)
ans++;
if (id[i] - od[i] == 1)
in++;
else if (od[i] - id[i] == 1)
on++;
else if (abs(id[i] - od[i]) > 1)
break;
}
// printf("%d %d %d %d\n", i, ans, in, on);
if (i < maxn || ans > 0 || in > 1 || on > 1)
printf("The door cannot be opened.\n");
else
printf("Ordering is possible.\n");
}//while
return 0;
}
#include <cstdio>
#include <cstdlib>
#include <cstring>
const int maxn = 30;
int f[maxn], g[maxn][maxn], id[maxn], od[maxn];
int t, n, root;
int Find(int x) {
if (x != f[x])
return f[x] = Find(f[x]);
return x;
}
int main () {
scanf("%d", &t);
while (t--) {
char word[1001];
scanf("%d", &n);
for (int i = 0; i < maxn; i++) {
f[i] = i;
id[i] = 0;
od[i] = 0;
for (int j = 0; j < maxn; j++)
g[i][j] = 0;
}
for (int i = 0; i < n; i++) {
scanf("%s", word);
int a = word[0] - 'a', b = word[strlen(word) - 1] - 'a';
g[a][b]++;
od[a]++;
id[b]++;
f[Find(a)] = Find(b);
root = Find(b);
}
int i, ans = 0, flag = 1, in = 0, on = 0;
for (i = 0; i < maxn; i++)
if (id[i] || od[i]) {
if (Find(f[i]) != root)
ans++;
if (id[i] - od[i] == 1)
in++;
else if (od[i] - id[i] == 1)
on++;
else if (abs(id[i] - od[i]) > 1)
break;
}
// printf("%d %d %d %d\n", i, ans, in, on);
if (i < maxn || ans > 0 || in > 1 || on > 1)
printf("The door cannot be opened.\n");
else
printf("Ordering is possible.\n");
}//while
return 0;
}
补充：软件开发 , C++ ,
