本文主要是介绍10129 - Play on Words （UVA），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接如下：
Online Judge
欧拉道路的题。
有向图满足欧拉道路有两个条件：1，图是连通的（无向边意义上）；2，最多只能有两个点的出度不等于入度，而且其中一个点的出度比入度大1，一个点的入度比出度大1.
连通是在无向边意义上连通，所以第16行需要 mat[k][i] || mat[i][k] ，只要单方向有路，就算连通。（一个测试数据：
msm
mac
csd
dsa
asd
如果 mat[k][i] || mat[i][k] 写成 mat[k][i] ，这组数据答案会有问题。
我的代码如下：
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
// #define debugint T, N;
std::string str;
int degree[26];
int mat[26][26];
int visited[26];void dfs(int k){visited[k] = 0;for (int i = 0; i < 26; ++i){if (visited[i] && (mat[k][i] || mat[i][k])){dfs(i);}}
}int main(){#ifdef debugfreopen("0.txt", "r", stdin);freopen("1.txt", "w", stdout);#endifscanf("%d", &T);while (T--){std::fill(degree, degree + 26, 0);std::fill(mat[0], mat[0] + 26 * 26, 0);std::fill(visited, visited + 26, 0);scanf("%d", &N);while (N--){std::cin >> str;degree[str[0] - 'a']++;degree[str.back() - 'a']--;mat[str[0] - 'a'][str.back() - 'a']++;visited[str[0] - 'a'] = 1;visited[str.back() - 'a'] = 1;}std::map<int, int> mp;bool flag = true;for (int i = 0; i < 26; ++i){if (degree[i] < -1 || degree[i] > 1){flag = false;break;}if (degree[i] == -1){mp[-1]++;} else if (degree[i] == 1){mp[1]++;}}if (!flag || mp[-1] > 1 || mp[1] > 1 || mp[-1] != mp[1]){printf("The door cannot be opened.\n");continue;}int cnt = 0;for (int i = 0; i < 26; ++i){if (visited[i]){cnt++;dfs(i);}}if (cnt == 1){printf("Ordering is possible.\n");} else {printf("The door cannot be opened.\n");}}#ifdef debugfclose(stdin);fclose(stdout);#endifreturn 0;
}这篇关于10129 - Play on Words （UVA）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
