题目

求算法：欧拉路
Description
定义：图G的欧拉回路是包含图G所有边的一个简单回路,而欧拉路径则是包含所有边的一个简单路径.
现在,告诉你一个无向图G,请你写段程序来判断该图G是否存在欧拉回路或者欧拉路径.
Input
第一行为两个整数N（0< N < 50）、M(0 < M < 1000),表示图G的结点数和边数.
接着M行,每行两个整数a,b.表示结点a和结点b之间有边.
图G的结点编号为0到N-1.
Output
输出仅有一行.如果图G存在欧拉回路,你需要输出“Circuit”；如果没有欧拉回路,但是存在欧拉路径,你需要输出“Path”；否则你需要输出“None”.
Sample Input
5 6
0 1
0 2
1 2
2 3
2 4
3 4
Sample Output
Circuit
Source

提问时间：2021-02-19

答案

欧拉回路 【定义】
图G的一个回路,若它恰通过G中每条边一次,则称该回路为欧拉(Euler)回路.
具有欧拉回路的图称为欧拉图（简称E图）.
【相关结论】
定理：
一个无向图是欧拉图,当且仅当该图所有顶点度数都是偶数.
一个有向图是欧拉图,当且仅当该图所有顶点度数都是0.
求欧拉回路的一种解法
下面是无向图的欧拉回路输出代码：注意输出的前提是已经判断图确实是欧拉回路.
int num = 0;//标记输出队列
int match[MAX];//标志节点的度,无向图,不区分入度和出度
void solve(int x)
l{
l if(match[x] == 0)
l
l Record[num++] = x;
l
l else
l {
l for(int k =0;k