P3545 一笔画问题
描述
如果一个图存在一笔画,则一笔画的路径叫做欧拉路,如果最后又回到起点,那这个路径叫做欧拉回路。
根据一笔画的两个定理,如果寻找欧拉回路,对任意一个点执行深度优先遍历;找欧拉路,则对一个奇点执行dfs,时间复杂度为,为边数,是点数。
输入
第一行 ,,有个点,条边,以下行描述每条边连接的两点。
输出
欧拉路或欧拉回路,输出一条路径即可。
样例输入
样例输出
如果一个图存在一笔画,则一笔画的路径叫做欧拉路,如果最后又回到起点,那这个路径叫做欧拉回路。
根据一笔画的两个定理,如果寻找欧拉回路,对任意一个点执行深度优先遍历;找欧拉路,则对一个奇点执行dfs,时间复杂度为,为边数,是点数。
第一行 ,,有个点,条边,以下行描述每条边连接的两点。
欧拉路或欧拉回路,输出一条路径即可。