#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 11 5 4 3 2 1