题目粗心

给定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;}