目的:判断是否是Eulerian Path
输入:
每个点
每个边
输出:
判断是哪种情况
算法:
用hash表统计每个点的度。如果全为偶数,则为Eulerian
如果有两个点的度为奇数,则为semi-Eulerian
如果不是以上的情况,则为non-Eulerian
而且判定要为连通图,如果不是,则为non-Eulerian
#include<stdio.h>
#include<vector>using namespace std;int N,M;
vector<int> hash1[510];
int vis[510] = {0};void dfs(int now)
{vis[now] = 1;for(int i=0;i<hash1[now].size();i++){int u = hash1[now][i];if(vis[u]==0){dfs(u);}}
}int main()
{scanf("%d%d",&N,&M);for(int i=0;i<M;i++){int u,v;scanf("%d%d",&u,&v);hash1[u].push_back(v);hash1[v].push_back(u);}int cnt = 0,flag = 0;dfs(1);for(int i=1;i<=N;i++){printf("%d",hash1[i].size());if(hash1[i].size()%2==1){cnt++;}if(vis[i]==0){flag = 1;}if(i!=N){printf(" ");}else{printf("\n");}}if(cnt==0&&flag==0){printf("Eulerian\n");}else if(cnt==2&&flag==0){printf("Semi-Eulerian\n");}else{printf("Non-Eulerian\n");}return 0;
}
反思:记住前提是连通图。