题目1027：欧拉回路
时间限制：1 秒
内存限制：32 兆
特殊判题：否
提交：2844
解决：1432
- 题目描述：
- 欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个图，问是否存在欧拉回路？
- 输入：
- 测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是节点数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
注意：代码中的i要从1开始，要与题目匹配！！
欧拉回路定义：
若图G中存在这样一条路径，使得它恰通过G中每条边一次,则称该路径为欧拉路径。若该路径是一个圈（首尾相连），则称为欧拉(Euler)回路。
判断是否存在欧拉回路的准则：
有向图：图连通，所有的顶点出度=入度。
无向图：图连通，所有顶点都是偶数度。
程序实现一般是如下过程：
1.利用并查集判断图是否连通，即判断p[i] < 0的个数，如果大于1，说明不连通。
2.根据出度入度个数，判断是否满足要求。
3.利用dfs输出路径。
学习代码：
/*************************************************** 题目描述：
欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个图，问是否存在欧拉回路？ 输入：
测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是节点数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 **************************************************/
#include <cstdio>
#include <cstring> using namespace std; const int N = + ; int n, m;
int g[N][N];
int degree[N];
int p[N]; int union_find(int x);
void disjoint_union(int a, int b);
bool check(); int main()
{
#ifndef ONLINE_JUDGE
freopen("e:\\uva_in.txt", "r", stdin);
#endif // ONLINE_JUDGE while (scanf("%d", &n) == )
{
if (n == )
break; scanf("%d", &m);
memset(degree, , sizeof(degree));
memset(p, -, sizeof(p)); for (int i = ; i < m; i++) {
int a, b;
scanf("%d%d", &a, &b);
degree[a]++;
degree[b]++;
disjoint_union(a, b);
} if (check())
printf("1\n");
else
printf("0\n");
}
return ;
} int union_find(int x)
{
if (p[x] < )
return x; return p[x] = union_find(p[x]);
} void disjoint_union(int a, int b)
{
int pa = union_find(a);
int pb = union_find(b); if (pa == pb)
return; if (pa < pb)
p[pb] = pa;
else
p[pa] = pb;
} bool check()
{
int cnt = ;
for (int i = ; i <= n; i++) {
cnt += (p[i] < );
if (degree[i] & )
return false;
} if (cnt != )
return false; return true;
}
自己的代码：
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <vector>
#include <stack>
#include <iostream>
using namespace std;
int fa[],degree[];
int findfa(int a){
if(fa[a]!=a){
fa[a]=findfa(fa[a]);
}
return fa[a];
}
int main(){
//freopen("D:\\INPUT.txt","r",stdin);
int n,m;
while(scanf("%d",&n)!=EOF){
if(!n){
break;
}
memset(degree,,sizeof(degree));
scanf("%d",&m);
int i;
for(i=;i<=n;i++){
fa[i]=i;
}
int u,v;
for(i=;i<m;i++){
scanf("%d %d",&u,&v);
degree[u]++;
degree[v]++;
int fu=findfa(u);
int fv=findfa(v);
if(fu>fv){
fa[fv]=fu;
}
else{
fa[fu]=fv;
}
}
int num=;
for(i=;i<=n;i++){
if(fa[i]==i){
num++;
}
}
if(num!=){//整体不联通,整个图不止一个集合.好好体会！！
cout<<<<endl;
continue;
}
int odd=;
for(i=;i<=n;i++){
if(degree[i]%){
odd++;
}
}
if(odd){//不是所有点的度数均为偶数
cout<<<<endl;
continue;
}
//全图联通并且所有点的度数均为偶数
cout<<<<endl;
}
return ;
}