本文主要是介绍UVA 10596 Morning Walk 简单的k欧拉回路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
UVA 10596 Morning Walk
简单的欧拉回路，用并查集判断图是否每个结点连在同一片，然后判断每个节点度数是否都为偶数
解法：没什么好说的直接上代码， 不过要注意的是输出格式
#include <stdio.h>
#include <string.h>
int n, m;
int ru[205];
int chu[205];
int vis[205];
int a, b;
int judge;
int parent[205];
int cent;
int find(int x)
{if (x != parent[x])return find(parent[x]);elsereturn x;
}void uion(int a, int b)
{a = find(a);b = find(b);if (a != b)parent[a] = b;
}int main()
{while(scanf("%d%d", &n, &m) != EOF){int r = m;judge = 0;cent = 0;memset(vis, 0, sizeof(vis));memset(parent, 0, sizeof(parent));memset(ru, 0, sizeof(ru));memset(chu, 0, sizeof(chu));for (int i = 0; i < n; i ++)parent[i] = i;while (m --){scanf ("%d%d", &a, &b);ru[b] ++;chu[a] ++;vis[a] = vis[b] = 1;uion(a, b);}for (int i = 0; i < n; i ++){if ((ru[i] + chu[i]) % 2){judge = 1;break;}}if (judge == 0){for (int i = 0; i < n; i ++){if (vis[i]){for (int j = 0; j < n; j ++){if (vis[j]){if (find(i) != find(j)){judge = 1;break;}}}}if (judge)break;}}if (judge || r == 0)printf("Not Possible\n");if (judge == 0 && r != 0)printf("Possible\n");} return 0;
}这篇关于UVA 10596 Morning Walk 简单的k欧拉回路的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
