例题6-16 单词（Play On Words, UVa 10129)

本文主要是介绍例题6-16 单词（Play On Words, UVa 10129)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接：https://vjudge.net/problem/UVA-10129
分类：图
备注：欧拉路

有向欧拉道路的条件：1，底图(忽略边方向之后得到的无向图)连通；2.度要满足欧拉路的条件。

代码如下：

#include<iostream>
#include<cstring>
#include<string>
#include<map>
using namespace std;
const int maxn = 100000 + 5;
int T, N, du[30], g[30][30];
string s;
int main(void) {cin >> T;while (T--) {cin >> N;map<char, int>id;memset(du, 0, sizeof(du));for (char i = 0; i < 26; i++)for (char j = 0; j < 26; j++)g[i][j] = (i == j ? 1 : 0);int cnt = 0;for (int i = 0; i < N; i++) {cin >> s;if (!id.count(s[0])) id[s[0]] = cnt++;if (!id.count(s.back())) id[s.back()] = cnt++;int u = id[s[0]], v = id[s.back()];du[u]++; du[v]--;g[u][v] = g[v][u] = 1;}int in = 0, out = 0;for (int i = 0; i < cnt; i++) {if (du[i] == 1) in++;else if (du[i] == -1)out++;else if (du[i] != 0) {out = 1; in = -1; break;}}if (out == in && (in == 1 || in == 0)) {for (int k = 0; k < cnt; k++)for (int i = 0; i < cnt; i++)for (int j = 0; j < cnt; j++)g[i][j] = g[i][j] || (g[i][k] && g[k][j]);bool isTong = true;for (int i = 0; i < cnt; i++)for (int j = 0; j < cnt; j++)if (!g[i][j]) isTong = false;if (isTong)cout << "Ordering is possible.\n";else cout << "The door cannot be opened.\n";}else cout << "The door cannot be opened.\n";}return 0;
}

这篇关于例题6-16 单词（Play On Words, UVa 10129)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---