U318869 一笔画问题
题目描述
如果一个图存在一笔画,则一笔画的路径叫做欧拉路,如果最后又回到起点,那这个路径叫做欧拉回路。
根据一笔画的两个定理,如果寻找欧拉回路,对任意一个点执行深度优先遍历;找欧拉路,则对一个奇点执行dfs,时间复杂度为 $O(m+n)$,$m$ 为边数,$n$ 是点数。
----------------------------------------------------------------------------------------------------------------
PS:如果图G中的一个路径包括每个边恰好一次,则该路径称为欧拉路径(Euler path)。
如果一个回路是欧拉路径,则称为欧拉回路(Euler circuit)
具有欧拉回路的图称为欧拉图(简称E图)。
欧拉由此提出 了著名的欧拉定理。
1)欧拉路:通过图中所有边的路径。
2)欧拉回路:闭合的欧拉路。
3)欧拉图:包含欧拉回路的图。
输入格式
第一行 $n$,$m$,有 $n$ 个点,$m$ 条边,以下 $m$ 行描述每条边连接的两点。
输出格式
欧拉路或欧拉回路,输出一条路径即可。(字典序最小)
说明/提示
【数据范围】
对于 $100%$ 的数据:$1 < n \lt 100$,$1 < m \lt 2000$。