欧拉回路

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

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
 
Recommend
We have carefully selected several similar problems for you:  1877 1881 1863 1875 1864
 
 
 
 
 
 
附:
 
ps赤裸裸的欧拉回路,下面两个没有注视是我写的,没有注视,可以作为模板,带有注视的是网上的,便于理解
 
 
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=;
int map[maxn][maxn];
bool vis[maxn];
int indegree[maxn],father[maxn];
int n,m;
void init(){
for(int i=;i<=n;i++)
father[i]=i;
}
int find(int u){
if(father[u]!=u)
father[u]=find(father[u]);
return father[u];
}
void Union(int x,int y){
int t1=find(x);
int t2=find(y);
if(t1!=t2)
father[t1]=t2;
}
int main(){ while(scanf("%d",&n)&&n){
init();
memset(map,,sizeof(map));
memset(indegree,,sizeof(indegree));
memset(vis,false,sizeof(vis));
scanf("%d",&m);
for(int i=;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
map[u][v]=map[v][u]=;
Union(u,v);
indegree[u]++;
indegree[v]++;
}
bool flag=false;
int sum=;
for(int i=;i<=n;i++){
if(father[i]==i){
sum++;
}
if(indegree[i]%==){
flag=true;
break;
}
} if(flag==true||sum!=)
printf("0\n");
else
printf("1\n"); }
return ;
}
 
    感谢大神
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=;
int map[maxn][maxn];
bool vis[maxn];
int indegree[maxn];
int n,m;
void dfs(int u){
vis[u]=true;
for(int i=;i<=n;i++)
if(!vis[i]&&map[u][i])
dfs(i);
return ;
}
int main(){
while(scanf("%d",&n)&&n){
scanf("%d",&m);
memset(map,,sizeof(map));
memset(vis,false,sizeof(vis));
memset(indegree,,sizeof(indegree));
for(int i=;i<m;i++){
int u,v;
scanf("%d%d",&u,&v);
indegree[u]++;
indegree[v]++;
map[u][v]=map[v][u]=;
} dfs();
int i;
for( i=;i<=n;i++){
if(!vis[i]||indegree[i]%==)
break;
}
if(i>n)
printf("1\n");
else
printf("0\n");
}
return ;
}
//本题主要考察欧拉回路的两个充要条件:1.联通图 2.顶点度数都为偶数 (两个条件缺一不可)

#include<stdio.h>
#include<string.h> int graph[][]; //采用邻接矩阵存储图
int visit[]; //在遍历时标记该点是否被访问过
int degree[]; //存储节点的度 void DFS(int v, int n) { //深度优先遍历,递归
visit[v] = ;
for(int i=; i<=n; i++)
if(graph[v][i] && visit[i]==)
DFS(i,n);
} int main() {
//freopen("in.txt","r",stdin);
int n, m;
while(scanf("%d %d",&n,&m)!=EOF && n) {
memset(graph,,sizeof(graph)); //清零
memset(visit,,sizeof(visit));
memset(degree,,sizeof(degree));
int a, b, i;
int flag = ; //标记是否存在欧拉回路
for(i=; i<m; i++) {
scanf("%d %d",&a,&b);
graph[a][b] = graph[b][a] = ; //"1"表示两点属于邻接关系
degree[a]++; degree[b]++;
}
DFS(,n);
for(i=; i<=n; i++) {
if(visit[i] == ) {
flag = ; //若有点未曾被访问,即一次深度遍历有未访问的点,则不存在欧拉回路
break;
}
if(degree[i] % != ) {
flag = ; //若有点的度不是偶数,则不存在欧拉回路
break;
}
}
if(flag)
printf("1\n");
else
printf("0\n");
} return ;
}
05-22 03:45