#1925. 欧拉回路
欧拉回路
题目描述:
输入一个无向连通图,判断这个图是否存在欧拉回路,如果没有则输出“no oula circle”,如果有,输出以结点1开始的一条欧拉回路,路径上结点序号优先小的。
欧拉路径:欧拉路径是指从图中任意一个点开始到图中任意一个点结束的路径,并且图中每条边都通过且只通过一次。
欧拉回路:欧拉回路是指起点和终点相同的欧拉路。
对于无向图,所有边都是连通的 (1)存在欧拉路径的充分必要条件:度数为奇数的点只能是0个或者2个,若为0个则存在欧拉回路,从任意一点开始均可找到欧拉回路。若为两个欧拉路径起点和终点为两个奇点。
(2)存在欧拉回路的充分必要条件:度数为奇数的点只能是0个
输入格式:
第一行一个整数 n 和 m,表示这个图有 n 个结点、m 条边,接下来 m 行,每行两个整数 ai和 aj,表示结点 ai 和 aj 之间有一条边。
输出格式:
如果不存在欧拉回路,请输出“no oula circle”,如果有欧拉回路,请输出结点 1 开始的欧拉回路的结点编号。
样例:
6 7
1 2
1 3
3 4
2 4
4 5
5 6
6 4
1 2 4 5 6 4 3 1
提示
1<n,m≤100