例题6-16(uva-10129)

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

每条边遍历一次且经过所有顶点，从起点开始 到 起点结束 ，称为欧拉图(欧拉回路)。
从起点开始 到 其他点 结束 ，称为半欧拉图(欧拉通路)。

无向图

1.是欧拉图 当且仅当 连通 且没有 奇度顶点(相邻边的数目)
2.是半欧拉图 当且仅当 连通 且 恰有两个奇度顶点

有向图
1.是欧拉图 当且仅当 基图连通(看做无向图) 且每个顶点的出度 等于 入度
2.是半欧拉图 当且仅当 基图连通 且仅有 两个奇度顶点，其中一个入度比出度大1，另一个出度比入度大1.

#include <iostream>
#include <istream>
#include <sstream>
#include <vector>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <cstring>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <numeric>
#include <chrono>
#include <ctime>
#include <cmath>
#include <cctype>
#include <string>
#include <cstdio>
#include <iomanip>#include <thread>
#include <mutex>
#include <condition_variable>
#include <functional>
#include <iterator>
using namespace std;
int deg[26], use[26],p[26];int GetFather(int u) {return u == p[u] ? u : p[u] = GetFather(p[u]);
}int main()
{int n,m;string in;vector<int> remain;cin >> n;while (n--) {int total = 26;cin >> m; cin.ignore();remain.clear();memset(deg, 0, sizeof(deg));memset(use, 0, sizeof(use));for (int i = 0; i < 26; ++i) p[i] = i;for (int i = 0; i < m; ++i) {getline(cin, in);int a = in.front() - 'a', b = in.back() - 'a';deg[a]++;deg[b]--;use[a] = use[b] = 1;int ua = GetFather(a),ub = GetFather(b);if (ua != ub) {p[ua] = p[ub]; total--;}}for (int i = 0; i < 26; ++i) {if (use[i] == 0) --total;else if (deg[i] != 0) remain.emplace_back(deg[i]);}if (total == 1 && (remain.empty() || (remain.size() == 2 && (remain.front() == -1 || remain.front() == 1)))) {cout << "Ordering is possible." << endl;}else {cout << "The door cannot be opened." << endl;}}return 0;
}

这篇关于例题6-16(uva-10129)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---