UVA 10129 欧拉回路
UVA 10129 欧拉回路
代码
`.
/*
* @Author: Axiuxiu
* @Date: 2021-11-03 15:24:40
* @LastEditors: Axiuxiu
* @LastEditTime: 2021-11-03 16:20:00
* @Description: 单词问题
*/
#include <stdio.h>
#include <string.h>
#define MAXN 1005
int G[26][26]; // 图矩阵
int vis[26][26]; // 访问矩阵, 矩阵内数值等于有向边条数
int get_letter_id(char ch)
{
return ch - 'a';
}
bool dfs(int u)
{
bool end = true;
for (int v = 0; v < 26; v++) {
if (vis[u][v]) {
end = false;
vis[u][v] -= 1;
if (dfs(v))
return true;
}
}
if (end) {
// 到达终点检查是否遍历所有边
for (int i = 0; i < 26; i++) {
for (int j = 0; j < 26; j++) {
if (vis[i][j])
return false;
}
}
return true;
}
else {
return false;
}
}
int main()
{
int n;
char word[MAXN];
while (scanf("%d", &n) == 1) {
memset(G, 0, sizeof(G));
// 读取n个单词
for (int i = 0; i < n; i++) {
scanf("%s", word);
int u = get_letter_id(word[0]);
int len = strlen(word);
int v = get_letter_id(word[len - 1]);
G[u][v] += 1;
}
// 深度优先遍历
bool flag = false;
for (int u = 0; u < 26; u++) {
// 初始化访问数组
memcpy(vis, G, sizeof(G));
if (dfs(u)) {
puts("Ordering is possible.");
flag = true;
break;
}
}
if (!flag) {
puts("The door cannot be opened.");
}
}
}