POJ 1300 欧拉通路&欧拉回路 - c++编程基础

系统的学习一遍图论！从这篇博客开始！

先介绍一些概念。

无向图：

G为连通的无向图，称经过G的每条边一次并且仅一次的路径为欧拉通路。

如果欧拉通路是回路（起点和终点相同），则称此回路为欧拉回路。

具有欧拉回路的无向图G称为欧拉图。

有向图：

D为基图连通的有向图，则称经过D的每一条边并且仅一次的路径为有向欧拉通路。

如果该通路是回路，则称为有向欧拉回路。

具有有向欧拉回路的有向图D称为有向欧拉图。

无向图判断欧拉通路：G为连通图，且仅有两个奇度的节点或者无奇度节点。

如果有两个奇度的点，那么这两点必定为欧拉通路的起点和终点。

如果没有奇度的节点，那么该图一定有欧拉回路。

有向图判断欧拉通路：D的基图连通，并且所有节点的出度和入度相同，那么该图存在有向欧拉回路。

如果仅有两个节点的出度和入度之差为1和-1，那么该图一定存在欧拉通路，并且一定以入度出度之差为-1的点为起点，入度出度之差为1的点为终点。

/************************************************************以上概念******************************************************************/

接下来介绍这道题。

题意就是能否从一个点出发，经过所有的边，回到节点0。

思路：就是判断一下，如果起点就是0，那么就是求是否存在欧拉回路。

如果起点不是0，那么就是求是否存在欧拉通路，并且欧拉通路的起点终点为0和输入的起点。

#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#define PI acos(-1.0)   
#define Max 2505   
#define inf 1<<28   
#define LL(x) ( x << 1 )   
#define RR(x) ( x << 1 | 1 )   
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )   
#define ll long long   
#define mem(a,b) memset(a,b,sizeof(a))   
#define mp(a,b) make_pair(a,b)   
#define PII pair   
using namespace std;  
  
  
inline void RD(int &ret) {  
    char c;  
    do {  
        c = getchar();  
    } while(c < '0' || c > '9') ;  
    ret = c - '0';  
    while((c=getchar()) >= '0' && c <= '9')  
        ret = ret * 10 + ( c - '0' );  
}  
inline void OT(int a){  
    if(a >= 10)OT(a / 10) ;  
    putchar(a % 10 + '0') ;  
}  
#define N 1111   
char in[111] ;  
int degree[N] ;  
int main() {  
    while(cin >> in){  
        if(in[0] == 'E')break ;  
        mem(degree , 0) ;  
        int n , m ;  
        cin >> n >> m ;  
        getchar() ;  
        int sum = 0 ;  
        for (int i = 0 ; i < m ;i ++ ){  
            int now ;  
            gets(in) ;  
            int l = strlen(in) ;  
            if(!l)continue ;  
            int num = 0 ;  
            for (int j = 0  ;j < l ;j ++ ){  
                if(in[j] == ' '){  
                    degree[i] ++ ;  
                    degree[num] ++ ;  
                    sum ++ ;  
                    num = 0 ;  
                }  
                else {  
                    num = num * 10 + (in[j] - '0') ;  
                }  
            }  
            if(num){  
                degree[i] ++ ;  
                degree[num] ++ ;  
                sum ++ ;  
            }  
        }  
        cin >> in ;  
        int odd = 0 ;  
        int even = 0 ;  
        for (int i = 0 ; i < m ; i ++ ){  
            if(degree[i] & 1)odd ++ ;  
            else even ++ ;  
        }  
        if(!odd){  
            if(n == 0){  
                printf("YES %d\n",sum) ;  
            }  
            else {  
                puts("NO") ;  
            }  
        }  
        else {  
            if(odd == 2){  
                if((degree[n] & 1) && (degree[0] & 1) && (n != 0)){  
                    printf("YES %d\n" ,sum) ;  
                }  
                else {  
                    puts("NO") ;  
                }  
            }else {  
                puts("NO") ;  
            }  
        }  
    }  
    return 0 ;  
}  

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define PI acos(-1.0)
#define Max 2505
#define inf 1<<28
#define LL(x) ( x << 1 )
#define RR(x) ( x << 1 | 1 )
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define PII pair
using namespace std;


inline void RD(int &ret) {
    char c;
    do {
        c = getchar();
    } while(c < '0' || c > '9') ;
    ret = c - '0';
    while((c=getchar()) >= '0' && c <= '9')
        ret = ret * 10 + ( c - '0' );
}
inline void OT(int a){
    if(a >= 10)OT(a / 10) ;
    putchar(a % 10 + '0') ;
}
#define N 1111
char in[111] ;
int degree[N] ;
int main() {
    while(cin >> in){
        if(in[0] == 'E')break ;
        mem(degree , 0) ;
        int n , m ;
        cin >> n >> m ;
        getchar() ;
        int sum = 0 ;
        for (int i = 0 ; i < m ;i ++ ){
            int now ;
            gets(in) ;
            int l = strlen(in) ;
            if(!l)continue ;
            int num = 0 ;
            for (int j = 0  ;j < l ;j ++ ){
                if(in[j] == ' '){
                    degree[i] ++ ;
                    degree[num] ++ ;
                    sum ++ ;
                    num = 0 ;
                }
                else {
                    num = num * 10 + (in[j] - '0') ;
                }
            }
            if(num){
                degree[i] ++ ;
                degree[num] ++ ;
                sum ++ ;
            }
        }
        cin >> in ;
        int odd = 0 ;
        int even = 0 ;
        for (int i = 0 ; i < m ; i ++ ){
            if(degree[i] & 1)odd ++ ;
            else even ++ ;
        }
        if(!odd){
            if(n == 0){
                printf("YES %d\n",sum) ;
            }
            else {
                puts("NO") ;
            }
        }
        else {
            if(odd == 2){
                if((degree[n] & 1) && (degree[0] & 1) && (n != 0)){
                    printf("YES %d\n" ,sum) ;
                }
                else {
                    puts("NO") ;
                }
            }else {
                puts("NO") ;
            }
        }
    }
    return 0 ;
}