hdu 1878 欧拉回路 判断无向图是否存在欧拉回路

缘起

欧拉回路是图论中的重要概念。 与小时候奥数学过的”一笔画”问题密切联系. hdu 1878 欧拉回路

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个图，问是否存在
欧拉回路？

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

先把概念和相关的图论定理说清楚

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
欧拉回路就是给一个图(有向或者无向)，存在一条回路把所边经过且每条边只经过一次。
欧拉路径是一条路经过所有的边并且每条边只经过一次。
欧拉路径不一定是回路，如果是回路的话, 欧拉路径就是欧拉回路. 即欧拉回路是欧拉路径的特例.
欧拉路径就是小时候学奥数的"一笔画"问题 ，也是瑞士大数学家欧拉研究哥尼斯堡七桥问题时得到的成果。

对于无向图：
   前提是连通图	
　　存在欧拉回路的充要条件：每个点的度都为偶数；
　　存在欧拉路径的充要条件：有且只有两个点的度为一，且这两个点分别为起点和终点；

对于有向图：
   前提是此图是有根图（即存在一个顶点, 从它出发可以抵达所有其他顶点）
　　存在欧拉回路的充要条件：每个点出度等于入度；
　　存在欧拉路径的充要条件：存在一个点出度比入度多一作为起点，存在一点入度比出度多一作为终点，其余点出
　　度等于入度；

至于欧拉回路的求法，我另写文章. 本题显然就是无向图是否存在欧拉回路的问题. 那么首先

  1. 判断图是否连通，这是无向图存在欧拉回路的前提.
  2. 计算每个顶点的度, 看看是不是都是偶数. 如果是的话, 则存在, 否则不存在.

第二步是trival的. 第一步可以使用dfs、bfs、并查集三种算法判断. 下面使用三种姿势艹它.

dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
//#include "stdafx.h"

#include <stdio.h>
#include <vector>
#include <string.h>
using namespace std;
//#define LOCAL

vector<int> g[1005]; // 邻接链表法
typedef vector<int>::iterator vit;
int n,m, deg[1005],res;
bool v[1005]; // 是否被访问过

void dfs(int i)
{
	v[i] = true;
	res--;
	for (vit x = g[i].begin(); x!=g[i].end(); x++)
	{
		if (!v[*x])
		{
			dfs(*x);
		}
	}
}

int xxx() // 判断是否存在欧拉回路
{
	for (int i = 1; i<=n;i++)
	{
		if (deg[i]&1)
		{
			return 0;
		}
	} // 这个先放在前面判断, 虽然连通是无向图存在欧拉回路的前提, 但是还是先判断度, 因为它更快
	res = n; // 经过dfs之后剩下的点的个数
	dfs(1);
	return res?0:1; // 连通则存在欧拉回路, 否则不存在
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	while(scanf("%d",&n), n)
	{
		for (int i = 1; i<=n ;i++)
		{
			g[i].clear();
		}
		memset(deg, 0, sizeof(deg));
		scanf("%d", &m);
		while(m--)
		{
			int i,j;
			scanf("%d%d", &i, &j);
			g[i].push_back(j);
			g[j].push_back(i);
			deg[i]++, deg[j]++;
		}
		printf("%d\n", xxx());
	}
	return 0;
}

ac情况

Status Accepted
Time 62ms
Memory 1360kB
Length 993
Lang G++
Submitted 2019-09-06 09:37:28
Shared
RemoteRunId 30517303

bfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
//#include "stdafx.h"

#include <stdio.h>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;
//#define LOCAL

vector<int> g[1005]; // 邻接链表法
typedef vector<int>::iterator vit;
int n,m, deg[1005],res;
bool v[1005]; // 是否被访问过

void bfs()
{
	queue<int> q;
	q.push(1);
	res--;
	v[1] = true;
	while(!q.empty())
	{
		int front = q.front();
		q.pop();
		for (vit x = g[front].begin(); x!=g[front].end(); x++)
		{
			if (!v[*x])
			{
				v[*x] = true;
				res--;
				q.push(*x);
			}
		}
	}
}

int xxx() // 判断是否存在欧拉回路
{
	for (int i = 1; i<=n;i++)
	{
		if (deg[i]&1)
		{
			return 0;
		}
	} // 这个先放在前面判断, 虽然连通是无向图存在欧拉回路的前提, 但是还是先判断度, 因为它更快
	res = n; // 经过dfs之后剩下的点的个数
	memset(v, 0, sizeof(v));
	bfs();
	return res?0:1; // 连通则存在欧拉回路, 否则不存在
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	while(scanf("%d",&n), n)
	{
		for (int i = 1; i<=n ;i++)
		{
			g[i].clear();
		}
		memset(deg, 0, sizeof(deg));
		scanf("%d", &m);
		while(m--)
		{
			int i,j;
			scanf("%d%d", &i, &j);
			g[i].push_back(j);
			g[j].push_back(i);
			deg[i]++, deg[j]++;
		}
		printf("%d\n", xxx());
	}
	return 0;
}

ac情况

Status Accepted
Time 62ms
Memory 1384kB
Length 1165
Lang G++
Submitted 2019-09-06 09:42:26
Shared
RemoteRunId 30517321

并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
//#include "stdafx.h"

#include <stdio.h>
#include <vector>
#include <string.h>
using namespace std;
//#define LOCAL

vector<int> g[1005]; // 邻接链表法
int n,m, deg[1005], f[1005];

int getf(int i)
{
	return f[i]<0?i:f[i] = getf(f[i]);
}

void merge(int i, int j)
{
	int fi = getf(i), fj = getf(j);
	if (fi==fj)
	{
		return;
	}
	if (f[fi]<f[fj])
	{
		f[fi]+=f[fj];
		f[fj] = fi;
	}
	else
	{
		f[fj]+=f[fi];
		f[fi] = fj;
	}
}

int xxx()
{
	memset(f, -1, sizeof(f));
	while(m--)
	{
		int i,j;
		scanf("%d%d", &i, &j);
		g[i].push_back(j);
		g[j].push_back(i);
		deg[i]++, deg[j]++;
		merge(i,j);
	}
	for (int i = 1; i<=n;i++)
	{
		if (deg[i]&1)
		{
			return 0;
		}
	}
	int sum = 0;
	for (int i = 1; i<=n;i++)
	{
		if (f[i]<0)
		{
			sum++;
			if (sum>1)
			{
				return 0;
			}
		}
	}
	return 1;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	while(scanf("%d",&n), n)
	{
		for (int i = 1; i<=n ;i++)
		{
			g[i].clear();
		}
		memset(deg, 0, sizeof(deg));
		scanf("%d", &m);
		printf("%d\n", xxx());
	}
	return 0;
}

ac情况

Status Accepted
Time 62ms
Memory 1368kB
Length 1077
Lang G++
Submitted 2019-09-06 10:02:00
Shared
RemoteRunId 30517407