PAT [1126] Eulerian path (25)

发表于 | 分类于

In graph theory, an Eulerian path is a path in a graph which visits every edge exactly once. Similarly, an Eulerian circuit is an Eulerian path which starts and ends on the same vertex. They were first discussed by Leonhard Euler while solving the famous Seven Bridges of Konigsberg problem in 1736. It has been proven that connected graphs with all vertices of even degree have an Eulerian circuit, and such graphs are called Eulerian. If there are exactly two vertices of odd degree, all Eulerian paths start at one of them and end at the other. A graph that has an Eulerian path but not an Eulerian circuit is called semi-Eulerian. (Cited from https://en.wikipedia.org/wiki/Eulerian_path)

Given an undirected graph, you are supposed to tell if it is Eulerian, semi-Eulerian, or non-Eulerian.

Input Specification:

Each input file contains one test case. Each case starts with a line containing 2 numbers N (<= 500), and M, which are the total number of vertices, and the number of edges, respectively. Then M lines follow, each describes an edge by giving the two ends of the edge (the vertices are numbered from 1 to N).

Output Specification:

For each test case, first print in a line the degrees of the vertices in ascending order of their indices. Then in the next line print your conclusion about the graph – either “Eulerian”, “Semi-Eulerian”, or “Non-Eulerian”. Note that all the numbers in the first line must be separated by exactly 1 space, and there must be no extra space at the beginning or the end of the line.

Sample Input 

1
2
3
4
5
6
7
8
9
10
11
12
13
7 12
5 7
1 2
1 3
2 3
2 4
3 4
5 2
7 6
6 3
4 5
6 4
5 6

Sample Output 

1
2
2 4 4 4 4 4 2
Eulerian

Algorithm:

  1. 欧拉通路、欧拉回路、欧拉图

无向图：
1) 设G是连通无向图，则称经过G的每条边一次并且仅一次的路径为欧拉通路；
2) 如果欧拉通路是回路（起点和终点是同一个顶点），则称此回路为欧拉回路（Euler circuit）；
3) 具有欧拉回路的无向图G称为欧拉图（Euler graph）。

定理:无向图G存在欧拉通路的充要条件是：G为连通图，并且G仅有两个奇度结点（度数为奇数的顶点）或者无奇度结点。
推论:当G是仅有两个奇度结点的连通图时，G的欧拉通路必以此两个结点为端点。

有向图：
1) 设D是有向图，D的基图连通，则称经过D的每条边一次并且仅一次的有向路径为有向欧拉通路；
2) 如果有向欧拉通路是有向回路，则称此有向回路为有向欧拉回路（directed Euler circuit）；
3) 具有有向欧拉回路的有向图D称为有向欧拉图（directed Euler graph）。

定理：有向图D存在欧拉通路的充要条件是：
D为有向图，D的基图连通，并且所有顶点的出度与入度都相等；或者除两个顶点外，其余顶点的出度与入度都相等，而这两个顶点中一个顶点的出度与入度之差为1，另一个顶点的出度
与入度之差为-1。
推论：
1) 当D除出、入度之差为1，-1的两个顶点之外，其余顶点的出度与入度都相等时，D的有向欧拉通路必以出、入度之差为1的顶点作为始点，以出、入度之差为-1的顶点作为终点。
2) 当D的所有顶点的出、入度都相等时，D中存在有向欧拉回路。

欧拉通路的判定:
有向图：图连通，有一个顶点出度大入度1，有一个顶点入度大出度1，其余都是出度=入度。
无向图：图连通，只有两个顶点是奇数度，其余都是偶数度的。

欧拉回路的判定:
有向图：图连通，所有的顶点出度=入度。
无向图：图连通，所有顶点都是偶数度。

Learn：

0、可以不用构建树就可以输出，学会考虑在构建的过程中多做点文章

code

首先是构建树后再z字形层次打印树，多次一举代码也比较冗余：

c++
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
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<math.h>
using namespace std;

vector<vector<int> > G;
vector<bool> v; 

int count1=0;

void dfs_node(int node)
{
	v[node]=true;
	count1++;
	for(int i=0;i<G[node].size();i++)
		if(!v[G[node][i]])
			dfs_node(G[node][i]);
			
}

int main()
{

	int n,m;
	cin>>n>>m;
	G.resize(n+1);
	v.resize(n+1);
	
	for(int i=0;i<n+1;i++)
		v[i]=0;

	for(int i=0;i<m;i++)
	{
		int a,b;
		scanf("%d %d",&a,&b);
		G[a].push_back(b);
		G[b].push_back(a);
	}
	
	int num=0;
	for(int i=1;i<n+1;i++)
	{
		printf("%d ",G[i].size());
		if(G[i].size()%2==0)
			num++;	
	}
	
	dfs_node(1);
	
	if(count1==n&&num==n)
		printf("\nEulerian");
	else if(count1==n&&num==n-2)//两个是奇数是只有欧拉路径的 
		printf("\nsemi-Eulerian");
	else
		printf("\nNon-Eulerian");

	return 0;
}