Uva 10596 - Morning Walk 欧拉回路基础水题 并查集实现
题目给出图，要求判断不能一遍走完所有边，也就是无向图，题目分类是分欧拉回路，但其实只要判断度数就行了。
一开始以为只要判断度数就可以了，交了一发WA了。听别人说要先判断是否是联通图，于是用并查集并一起，然后判断是否有多个根。
用dfs的话就是深搜时标记下，最后看看有没有全部标记。我没用dfs做。
代码：
#include <cstdio>
const int maxn = 201;
int f[maxn];
int d[maxn];
int find(int x) {
if (x != f[x])
return f[x] = find(f[x]);
return x;
}
int main() {
int n, r;
while (scanf("%d%d", &n, &r) != EOF) {
bool ok = 1;
int ans = 0;
for (int i = 0; i < n; i++)
d[i] = 0, f[i] = i;
int a, b;
for (int i = 0; i < r; i++) {
scanf("%d%d", &a, &b);
f[find(a)] = find(b);
d[a]++;
d[b]++;
}//for
if (r <= 1 || n == 0)
ok = 0;
for (int i = 0; ok && i < n; i++)
if (f[i] == i && ans++ > 0)
ok = 0;
for (int i = 0; ok && i < n; i++)
if (d[i] % 2 != 0) {
ok = 0;
break;
}
if (ok)
printf("Possible\n");
else
printf("Not Possible\n");
}//while
return 0;
}
补充：软件开发 , C++ ,
