做题网站推荐: OpenJudge VIJOS UOJ CF JOYOI CODEVS 洛谷 RQNOJ BZOJ POJ HDU 牛客网

本站题目推荐: 高精度 模拟 排序 递推 贪心 递归 搜索 动态规划 数学 图论 数据结构 签到 实名认证 卡评测举报

输入输出 变量类型 顺序结构 选择结构 循环结构 一维数组 NOIP 资源下载


问题 2428. -- [C++一本通-图论算法]例题 一笔画问题

2428: [C++一本通-图论算法]例题 一笔画问题

时间限制: 1 Sec  内存限制: 128 MB
提交: 153  解决: 45
[上一题][提交][讨论版][状态][下一题]

题目描述

       如果一个图存在一笔画,则一笔画的路径叫做欧拉路,如果最后又回到起点,那这个路径叫做欧拉回路。

       我们定义奇点是指跟这个点相连的边数目有奇数个的点。对于能够一笔画的图,我们有以下两个定理。

      定理1:存在欧拉路的条件:图是连通的,有且只有2个奇点。

      定理2:存在欧拉回路的条件:图是连通的,有0个奇点。

     两个定理的正确性是显而易见的,既然每条边都要经过一次,那么对于欧拉路,除了起点和终点外,每个点如果进入了一次,显然一定要出去一次,显然是偶点。对于欧拉回路,每个点进入和出去次数一定都是相等的,显然没有奇点。

     求欧拉路的算法很简单,使用深度优先遍历即可。

     根据一笔画的两个定理,如果寻找欧拉回路,对任意一个点执行深度优先遍历;找欧拉路,则对一个奇点执行dfs,时间复杂度为O(m+n),m为边数,n为点数。

     以下是寻找一个图的欧拉路的算法实现:

输入

第一行:n,m,有n个点,m条边,两个数之间用空格隔开

以下m行描述每条边连接的两点。两个数之间用空格隔开

输出

欧拉路或者欧拉回路,两个数之间用空格隔开

样例输入

5 5
1 2
2 3
3 4
4 5
5 1

样例输出

1 5 4 3 2 1

提示

提示:n+m<50

标签

[上一题][提交][讨论版][状态][下一题]