http://dsalgo.openjudge.cn/graph/7/
描述欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路
给定一个无向图，请判断该图是否存在欧拉回路
输入 输入数据包含若干测试用例 每个测试用例的第一行是两个正整数，分别表示图的节点数N(1 < N < 1000)和边数M 随后的M行对应M条边，每行有两个正整数，分别表示这条边上的两个节点的编号（节点编号从1到N） 当N为0时输入结束 输出 每个测试用例的输出占一行，若存在欧拉回路则输出1，否则输出0 样例输入 3 3 1 2 1 3 2 3 3 2 1 2 2 3 0 样例输出 1 0
emmmmm，犯了一个很傻逼的错了
最后，这个判断一个图是否有欧拉回路的条件：1）图是连通的。 2）每个结点的度之和必须为偶数。
只有同时满足这两个条件，才能判断欧拉回路存在。
C++代码：
#include<iostream> #include<stdio.h> using namespace std; const int maxn = 1010; int n,m; int father[maxn]; int node[maxn]; int Find(int a){ while(a != father[a]){ father[a] = father[father[a]]; a = father[a]; } return a; } void Union(int a,int b){ int ax = Find(a); int bx = Find(b); if(ax != bx) father[ax] = bx; } int main(){ while(cin>>n){ if(n == 0) break; cin>>m; for(int i = 1; i <= n; i++){ father[i] = i; node[i] = 0; } int x,y; for(int i = 1;i <= m; i++){ cin>>x>>y; node[x]++; node[y]++; Union(x,y); } int cnt = 0; int flag = 1; int cnt1 = 0; for(int i = 1; i <= n; i++){ //要认真啊啊啊，i <= n 不是 i <= m..... if(father[i] == i){ cnt++; if(cnt == 2) flag = 0; } if(node[i] & 1) cnt1++; } if(cnt1 != 0) flag = 0; if(flag) cout<<1<<endl; else cout<<0<<endl; } return 0; }
转载于:https://www.cnblogs.com/Weixu-Liu/p/10920376.html
