好贷网好贷款

ZOJ 2016 欧拉路判定

发布时间:2016-12-4 3:48:15 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"ZOJ 2016 欧拉路判定",主要涉及到ZOJ 2016 欧拉路判定方面的内容,对于ZOJ 2016 欧拉路判定感兴趣的同学可以参考一下。

判定联通 出度入度即可 #include <set> #include <cmath> #include <queue> #include <stack> #include <string> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; const double PI = acos(-1.0); template <class T> inline T MAX(T a, T b){if (a > b) return a;return b;} template <class T> inline T MIN(T a, T b){if (a < b) return a;return b;} const int N = 111; const int M = 11111; const LL MOD = 1000000007LL; const int dir[4][2] = {1, 0, -1, 0, 0, -1, 0, 1}; const int INF = 0x3f3f3f3f; int ind[30], outd[30]; int vis[30], n, p[30], u[111111], v[111111]; int Find(int x) {if (p[x] < 0) return x; else return Find(p[x]);} void Union(int x, int y) { int temp = p[x] + p[y]; if (p[x] < p[y]) { p[y] = x; p[x] = temp; } else { p[x] = y; p[y] = temp; } } bool check() { memset(p, -1, sizeof(p)); int x, y, i, j, k; for (i = 0; i < n; ++i) { x = Find(u[i]); y = Find(v[i]); if (x != y) Union(x, y); } int first = -1; for (i = 0; i < 26; ++i) { if (!vis[i]) continue; x = Find(i); if (first == -1) first = x; else if (x != first) return false; } return true; } int main() { int T; scanf("%d", &T); while (T--) { int l, i, a; char str[1111]; scanf("%d", &n); memset(ind, 0, sizeof(ind)); memset(outd, 0, sizeof(outd)); memset(vis, 0, sizeof(vis)); for (i = 0; i < n; ++i) { scanf("%s", str); l = strlen(str); u[i] = str[0] - 'a'; v[i] = str[l - 1] - 'a'; vis[str[0]-'a'] = vis[str[l - 1] - 'a'] = 1; outd[str[0] - 'a']++; ind[str[l - 1] - 'a']++; } int f = 0, num1 = 0, num2 = 0; for (i = 0; i < 26; ++i) { if (ind[i] == outd[i]) continue; if (ind[i] == outd[i] + 1) num1++; else if (ind[i] + 1 == outd[i]) num2++; else break; } // if (check()) printf("!!!\n"); if (check() && i == 26 && ((num1 == 1 && num2 == 1) || (num1 == 0 && num2 == 0))) printf("Ordering is possible.\n"); else printf("The door cannot be opened.\n"); } return 0; }

上一篇:java_web 学习第一天(Servlet入门)
下一篇:贡献30本经典Linux学习和开发教程和资料,都是pdf完整版的

相关文章

相关评论