跳至正文
题库4016
#4016

1341. 【例题】一笔画问题

查看题目操作

1341. 【例题】一笔画问题

题目描述

如果一个图存在一笔画,则一笔画的路径叫做欧拉路,如果最后又回到起点,那这个路径叫做欧拉回路。 根据一笔画的两个定理,如果寻找欧拉回路,对任意一个点执行深度优先遍历;找欧拉路,则对一个奇点执行dfs,时间复杂度为O(m+n),m为边数,n是点数。

输入格式

第一行 n、m,1 < n < 100,1 < m < 2000;随后 m 行描述无向边的两个端点(编号1到n)。允许两点间存在多条边,每条边都需要走一次;没有自环。所有有边的结点连通,且奇度结点数为0或2,保证存在欧拉路;无边的孤立结点可忽略。

输出格式

输出一条欧拉路或欧拉回路,共 m+1 个结点编号,按访问顺序排列,每条输入边恰好使用一次。任意合法路径均可,不得输出额外内容。
5 5
1 2
2 3
3 4
4 5
5 1
1 5 4 3 2 1

来源

一本通在线评测 ybtbas-1341