题目给出图,要求判断不能一遍走完所有边,也就是无向图,题目分类是分欧拉回路,但其实只要判断度数就行了。
一开始以为只要判断度数就可以了,交了一发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;
}
分享到:
相关推荐
这里以构建一个度全部相同的欧拉回路,并输出欧拉回路的路径 1.构建欧拉回路 连通主要是靠树来保证,首先建立一个度为k的完全图,其中会有很多需要主要的地方 (1)首先构造树 =>保证顶点连通 (2)将度的点...
欧拉回路C++程序 随机输入任意点数,给出图中存在的欧拉回路
图论- 图的遍历- 欧拉通路与欧拉回路问题.rar
实现了欧拉回路的程序实现即遍历图输出欧拉回路
欧拉回路性质与应用探究欧拉回路性质与应用探究欧拉回路性质与应用探究
算法-欧拉回路(HDU-1878)(包含源程序).rar
图论——欧拉回路的Fleury算法 根据离散数学教材中思想 实现求欧拉回路。
欧拉回路,又称“一笔画”,是图论中可行遍性问题的一种。本文首先介绍了欧拉回路的相关理论知识,以及求欧拉回路的算法。然后通过几个实例,介绍了与欧拉回路相关的几类典型问题。最后对欧拉回路的模型进行了总结,...
本资源主要内容为有向图的无向图的欧拉回路的判定,使用的编程语言为JAVA,并采用邻接表作为图的存储结构,使用并查集判断图是否连通,利用图的遍历算法得到一条有效的欧拉回路,最后通过界面将欧拉路径动态显示在...
找欧拉回路,本程序实现了对一个欧拉图形找其欧拉回路
关于算法与图论中有向图的欧拉回路的判断,判断一个有向图是否有欧拉回路
对欧拉回路的实验报告,有利于大家更好地理解欧拉回路,对要实验报告的人很适合。本算法使用c语言编写的 如需其他语言请自行更改。
Catenyms poj hoj 欧拉回路输出路径
COMSOL 两相流 欧拉-欧拉 双流体模型
可以证明,当算法停止时所得的简单回路Wm=v0e1v1e2….emvm(vm=v0)为G中的一条欧拉回路,复杂度为O(e*e)……
2022级图论-欧拉回路和最短路_题解
自己用C写的无向图找欧拉回路的一个例子。主要用于数据结构的学习
欧拉回路题集,适用于算法爱好者,内含 欧拉回路的多种题型
寻找欧拉回路c++,不解释,大家都懂.最多可以生成230000个节点。大家试一下
有图论中的很多知识,比如图论概念,类型等,还有欧拉回路与汉密尔顿路