hdu1878欧拉回路(DFS+欧拉回路)

hdu1878欧拉回路(DFS+欧拉回路)

欧拉回路

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 10633    Accepted Submission(s): 3875

Problem Description

欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个图，问是否存在欧拉回路？

Input

测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是节点数N ( 1 < N < 1000 )和边数M；随后的M行对应M条边，每行给出一对正整数，分别是该条边直接连通的两个节点的编号（节点从1到N编号）。当N为0时输入结 束。

Output

每个测试用例的输出占一行，若欧拉回路存在则输出1，否则输出0。

Sample Input

3 3 1 2 1 3 2 3 3 2 1 2 2 3 0

Sample Output

1 0

Author

ZJU

Source

​​浙大计算机研究生复试上机考试-2008年​​

Recommend

We have carefully selected several similar problems for you:   ​​1880​​​  ​​​1881​​​  ​​​1864​​​  ​​​1859​​​  ​​​1876​​

​​Statistic​​ |

​​Submit​​ |

​​Discuss​​ |

​​Note​​

欧拉回路问题。

如果要满足欧拉回路有两个条件。1.所有顶点的度数全部是偶数2.必须保证是一个联通图

eg:

6 6

1 2

1 3

2 3

4 5

4 6

5 6

应该输出0。起初写的时候想着不用考虑这么复杂把。。就没有判断是不是一个联通图，结果wa了。。

第二次想着用vector邻接表判断联通图。又忘记初始化数组了

说明做题不能存在侥幸心理，要细心。

#include #include #include using namespace std;int vis[1005][1005],visit[1005];vectormap[1005];void dfs(int pos){ visit[pos]=1; for(int i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。