首页 > 其他 > 详细

九度:题目1027:欧拉回路

时间:2014-02-17 14:44:34      阅读:373      评论:0      收藏:0      [点我收藏+]

题目描述:
    欧拉回路是指不令笔离开纸面,可画过图中每条边仅一次,且可以回到起点的一条回路。现给定一个图,问是否存在欧拉回路?
输入:
    测试输入包含若干测试用例。每个测试用例的第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 <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define MAX 1005
int N,M;
int a,b;
int map[MAX][MAX];
bool vis[MAX];
 
bool dfs(int k,int n){
    if(n==N){
        if(map[k][a])return true;
        else return false;
    }
    for(int i=1;i<=N;i++){
        if(map[k][i]&&!vis[i]){
            vis[i]=true;
            if(dfs(i,n+1))return true;
            vis[i]=false;
        }
    }
    return false;
}
int main(){
    //freopen("C:\\in.txt","r",stdin);
    while(~scanf("%d",&N)&&N){
        scanf("%d",&M);
        memset(map,0,sizeof(map));
        memset(vis,0,sizeof(vis));
        for(int i=0;i<M;i++){
            scanf("%d%d",&a,&b);
            map[a][b]=map[b][a]=1;
        }
        vis[a]=true;
        printf("%d\n",dfs(a,1));
    }
    return 0;
}
/**************************************************************
    Problem: 1027
    User: starcuan
    Language: C++
    Result: Time Limit Exceed
****************************************************************/

所以,得从欧拉回路的性质出发,

1、欧拉回路必须能从1一直能连线到n的连通图,所以用并查集的话,就只能有1个集合

2、欧拉回路:

有向图:所有的顶点出度=入度。

无向图:所有顶点都是偶数度。

满足上面两个条件的话就一定是欧拉回路

所以,利用并查集和节点度数的奇偶判断就可知是否是欧拉回路

/*
题目1027:欧拉回路
 
*/
#include <iostream>
#include <string.h>
using namespace std;  
 
#define MAX 1005  
 
int N,M;  
int a,b;  
 
int field[MAX];  
int degree[MAX];  
   
int find(int x)  
{  
    if(field[x]==0)  
        return x;   
    field[x] = find(field[x]);     
    return field[x];       
}  
void make(int x,int y)//将x与y合并  
{  
    int f1=find(x);  
    int f2=find(y);  
    if(f1!=f2)  
        field[f2]=f1;  
} 
   
int main()  
{  
    //freopen("C:\\in.txt","r",stdin);
     
    while(cin>>N&&N)  
    {  
        cin>>M;  
        memset(field,0,sizeof(field));
        memset(degree,0,sizeof(degree));
       
        while(M--)  
        {  
            cin>>a>>b;
            ++degree[a];  //a的度(出度)++
            ++degree[b];   //b的度(入度)++
            make(a,b);//将a b合并
        }  
        int cnt = 0;  //集合的个数,等于1才满足欧拉回路
        int flag = 1;  
        for(int i=1;i<=N;++i)  
        {  
            if(field[i]==0)  cnt++;  
            if(degree[i]%2==1) flag=0;
        }  
        if(cnt!=1)  flag=0;  
        cout<<flag<<endl;                      
    }  
    return 0;  
}  
/**************************************************************
    Problem: 1027
    User: starcuan
    Language: C++
    Result: Accepted
    Time:130 ms
    Memory:1528 kb
****************************************************************/



九度:题目1027:欧拉回路

原文:http://blog.csdn.net/starcuan/article/details/19302633

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!