关于c++:PAT甲级1126-Eulerian-Path

题目粗心

给定N个顶点M条边的无向图，判断该图是Eulerian，semi-Eulerian还是non-Eulerian，并输入每一个顶点的度。

算法思路

首先得理清几个概念

• Eulerian path：恰好拜访图中所有顶点的门路
• Eulerian circuit：Eulerian path的终点和起点雷同
• Eulerian: 在一个连通图中所有顶点的度为偶数
• semi-Eulerian：连通图含有Eulerian path但没有 Eulerian circuit,即连通图中只有两个顶点的度为奇数
• non-Eulerian：既不是Eulerian也不是semi-Eulerian

对于顶点的度间接应用degree数组统计输入即可，而后咱们判断以后图是否是连通图，判断办法就是从任一终点应用深度优先搜寻，如果该连通重量的顶点数目和N雷同，就阐明该图连通，否则就不是连通图，输入Non-Eulerian，而后再统计每一个顶点的度是否是偶数，如果都是偶数，输入Eulerian，如果只有两个顶点的度为奇数，输入Semi-Eulerian，否则输入Non-Eulerian。

提交后果

AC代码

#include <cstdio>

using namespace std;


int G[505][505];
int degree[505];// 每一个顶点的度
bool visited[505];// 拜访标记数组
int cnt = 0;// 顶点为1的连通重量的顶点数目
int n,m;

void DFS(int start){
    visited[start] = true;
    ++cnt;
    for(int i=1;i<=n;++i){
        if(!visited[i]&&G[start][i]!=0){
            DFS(i);
        }
    }
}

void printDegree(){
    for(int i=1;i<=n;++i){
        printf("%d",degree[i]);
        if(i<n) printf(" ");
    }
    printf("\n");
}

int main() {
    scanf("%d %d",&n,&m);
    for(int i=0;i<m;++i){
        int a,b;
        scanf("%d %d",&a,&b);
        G[a][b] = G[b][a] = 1;
        ++degree[a];
        ++degree[b];
    }
    // 统计从顶点1登程的连通重量的顶点数
    DFS(1);
    printDegree();
    if(cnt!=n){
        // 该图不连通
        printf("Non-Eulerian");
    }else{
        int evenDegree = 0;// 度为偶数的顶点个数
        for(int i=1;i<=n;++i){
            if(degree[i]%2==0){
                ++evenDegree;
            }
        }
        if(evenDegree==n){
            printf("Eulerian");
        }else if(evenDegree==n-2){
            printf("Semi-Eulerian");
        }else{
            printf("Non-Eulerian");
        }
    }
    return 0;
}