首页 > 代码库 > hdu1878 欧拉回路(并查集)
hdu1878 欧拉回路(并查集)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1878
Problem Description
欧拉回路是指不令笔离开纸面,可画过图中每条边仅一次,且可以回到起点的一条回路。现给定一个图,问是否存在欧拉回路?
Input
测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数,分别是节点数N ( 1 < N < 1000 )和边数M;随后的M行对应M条边,每行给出一对正整数,分别是该条边直接连通的两个节点的编号(节点从1到N编号)。当N为0时输入结
束。
束。
Output
每个测试用例的输出占一行,若欧拉回路存在则输出1,否则输出0。
Sample Input
3 3 1 2 1 3 2 3 3 2 1 2 2 3 0
Sample Output
1 0
无向欧拉图的欧拉回路存在的充要条件:连通且没有奇点;
欧拉路径存在的充要条件:连通且奇点个数为2;
有向欧拉图的欧拉回路存在的充要条件:基图连通且所有顶点的入度等于出度;
欧拉路径存在的充要条件:基图连通且存在某顶点入度比出度多一,
另一顶点出度比入度多一,其余顶点入度等于出度。
代码如下:
#include <cstdio> #include <cstring> int father[1017]; int n, m; int find(int x) { return x==father[x]?x:father[x]=find(father[x]); } void init() { for(int i = 0; i <= n; i++) { father[i] = i; } } void Union(int x, int y) { int f1 = find(x); int f2 = find(y); if(f1 != f2) father[f2] = f1; } int main() { int i, j; int a, b; int cal[1017]; while(scanf("%d",&n)&& n) { init(); memset(cal,0,sizeof(cal)); if(n == 0) break; scanf("%d",&m); for(i = 0; i < m; i++) { scanf("%d%d",&a,&b); Union(a,b); cal[a]++,cal[b]++; } int flag = 0; int t = father[1]; for(i = 1; i <= n; i++) { if(cal[i]%2 == 1 || father[i] != t) { flag = 1; break; } } if(flag) printf("0\n"); else printf("1\n"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。