关于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;
}