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;
}

hdu1878 欧拉回路(并查集)

时间: 07-17

hdu1878 欧拉回路(并查集)的相关文章

hdu1878 欧拉回路 并查集

Problem Description 欧拉回路是指不令笔离开纸面,可画过图中每条边仅一次,且可以回到起点的一条回路.现给定一个图,问是否存在欧拉回路? Input 测试输入包含若干测试用例.每个测试用例的第1行给出两个正整数,分别是节点数N ( 1 < N < 1000 )和边数M:随后的M行对应M条边,每行给出一对正整数,分别是该条边直接连通的两个节点的编号(节点从1到N编号).当N为0时输入结束. Output 每个测试用例的输出占一行,若欧拉回路存在则输出1,否则输出0. Sample

HDU1116(欧拉回路+并查集)

先用并查集来判断图是否连通,然后再根据欧拉回路的出度和入度的性质来判断是否为欧拉回路. 关键是建边,我们可以把字符串看成是一条边,首字母为出发点,尾字母为目的点,建边. #include <stdio.h> #include <string.h> #include <string> #include <iostream> #include <algorithm> #include <vector> #include <math.

poj 2513 欧拉回路+并查集判断是否联通+Trie树

http://poj.org/problem?id=2513 最初看到 第一感觉---map  一看250000的数据量 果断放弃 然后记得以前看过,trie代替map,尤其当数据量特别大的时候 学到了: 1.Trie代替map的思想,可以在单词结尾的tree[i][tk]  这个i作为字符串对应的int值 ,当然这个int值也可以用于建立并查集 2.接上,通过并查集判断,所有的点在同一个集合图就是联通的,否则不联通,注意tree[i][tk]>0 表示是单词结尾, x=Find(x);//这句

HDU 1116 || POJ 1386 || ZOJ 2016 Play on Words (欧拉回路+并查集)

题目链接 题意 : 有很多门,每个门上有很多磁盘,每个盘上一个单词,必须重新排列磁盘使得每个单词的第一个字母与前一个单词的最后一个字母相同.给你一组单词问能不能排成上述形式. 思路 :把每个单词看成有首字母指向尾字母的有向边,每个字母看成一个点,题中要求等效于判断图中是否存在一条路径经过每一条一次且仅一次,就是有向欧拉通路.统计个顶点的出入度,如果每个点的出入度都相同,那就是欧拉回路,如果有两个奇数度,那就是欧拉通路,除此之外,都不能满足要求.还有别忘了判断是否连通,此时用到并查集,图中所有的边

UVA - 10129 Play on Words(欧拉回路+并查集)

2.解题思路:本题利用欧拉回路存在条件解决.可以将所有的单词看做边,26个字母看做端点,那么本题其实就是问是否存在一条路径,可以到达所有出现过的字符端点.由于本题还要求了两个单词拼在一起的条件是前一个单词的右端点和本单词的左端点一样.所以这是一个有向图.根据结论:有向图的底图(忽略边的方向后的图)必须连通:有向图中最多只能有两个端点的入度不等于出度,且必须是其中一点的入度比出度小1,另一点的入度比出度大1.因此先判断端点是否都连通,再判断每个端点的度数是否满足结论即可. 那么,如何判断连通性呢?

ACM: FZU 2112 Tickets - 欧拉回路 - 并查集

FZU 2112 Tickets Time Limit:3000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u Practice Description You have won a collection of tickets on luxury cruisers. Each ticket can be used only once, but can be used in either direction between

nyist 42 一笔画 (欧拉回路 + 并查集)

nyoj42 分析: 若图G中存在这样一条路径,使得它恰通过G中每条边一次,则称该路径为欧拉路径. 若该路径是一个圈,则称为欧拉(Euler)回路. 具有欧拉回路的图称为欧拉图(简称E图).具有欧拉路径但不具有欧拉回路的图称为半欧拉图. 先说一下欧拉路径.欧拉回路的充要条件: 1.无向连通图G是欧拉图,当且仅当G不含奇数度结点(G的所有结点度数为偶数): 2.无向连通图G含有欧拉通路,当且仅当G有零个或两个奇数度的结点: 3.有向连通图D是欧拉图,当且仅当该图为连通图且D中每个结点的入度=出度

poj 2513 欧拉回路+并查集推断是否联通+Trie树

http://poj.org/problem? id=2513 最初看到 第一感觉---map  一看250000的数据量 果断放弃 然后记得曾经看过.trie取代map.尤其当数据量特别大的时候 学到了: 1.Trie取代map的思想,能够在单词结尾的tree[i][tk]  这个i作为字符串相应的int值 .当然这个int值也能够用于建立并查集 2.接上.通过并查集推断.全部的点在同一个集合图就是联通的,否则不联通,注意tree[i][tk]>0 表示是单词结尾. x=Find(x);//这

hdu 1878 欧拉回路+并查集

欧拉回路: 通过图中每条边且只通过一次,并且经过每一顶点的回路. 无向图欧拉回路的判定:图连通:图中所有节点度均为偶数 有向图欧拉回路的判定:图连通:所有节点入度等于出度 这道题属于无向图,首先用并查集判断图的联通性,各点的度数用一个数组保存下来. 如果一个点的根结点和其他点的根结点不同,则图不联通,有点度数为奇数也不满足欧拉回路,则输出0,否则输出1. 1 #include<iostream> 2 #include<algorithm> 3 #include<cmath&g

HDU 1878 欧拉回路 (并查集+欧拉回路)

题目地址:HDU 1878 这个题要注意欧拉回路与欧拉通路的区别.在都保证连通性的前提下,欧拉回路要求每个点的度数都是偶数,而欧拉通路允许两个点的度数是奇数.所以这题用并查集判断连通性后判断下度数就可以了. 代码如下: #include <iostream> #include <string.h> #include <math.h> #include <queue> #include <algorithm> #include <stdlib