hdu 1878 欧拉回路(简单欧拉回路)

hdu 1878 欧拉回路(简单欧拉回路)

题目：​​Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 10649    Accepted Submission(s): 3884

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

入门级欧拉回路：

#include //无向图的欧拉回路判断：并查集+记录各节点的度#include //无向图欧拉回路：奇点个数=0 欧拉路径: 奇点个数=0||奇点个数=2#include using namespace std;const int maxn=1e3+5;int n,f[maxn],deg[maxn];int find(int x){ if(x==f[x]) return x; return f[x]=find(f[x]);}int main(){ //freopen("cin.txt","r",stdin); int m,a,b; while(cin>>n&&n){ memset(deg,0,sizeof(deg)); memset(f,0,sizeof(f)); scanf("%d",&m); for(int i=1;i<=m;i++){ scanf("%d %d",&a,&b); if(!f[a])f[a]=a; if(!f[b])f[b]=b; deg[a]++; deg[b]++; f[find(a)]=f[find(b)]; } int judge=0; for(int i=1;i<=n;i++){ if(f[i]==i) judge++; } if(judge>1) { puts("0"); continue; } judge=0; for(int i=1;i<=n;i++){ if(deg[i]&1) judge++; } if(judge==0) puts("1"); else puts("0"); } return 0;}

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