HDU 1878(1Y) (判断欧拉回路是否存在 奇点个数为0 + 一个联通分量 *【模板】)
欧拉回路
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 9797 Accepted Submission(s): 3554
束。
#include <stdio.h> #include <string.h> #include <iostream> #include <string> #include <algorithm> #define N 1000+2 using namespace std; bool map[N][N]; int odd[N]; bool vis[N]; int n; void dfs(int dd) //测试图的连通性 { for(int i=1; i<=n; i++) { if(!vis[i] && map[dd][i]==true ) { vis[i]=true; dfs(i); } } } int main() { int m; int i, j; int dd; //计数奇点的数目 int u,v; while(scanf("%d", &n)!=EOF) { if(n==0) break; scanf("%d", &m); for(i=0; i<=n; i++) { for(j=0; j<=n; j++) { map[i][j]=false; } } memset(odd, 0, sizeof(odd)); for(i=0; i<m; i++) { scanf("%d %d", &u, &v); map[u][v]=true; map[v][u]=true; odd[u]++; odd[v]++; } for(i=1; i<=n; i++) vis[i]=false; int ans=0; //计算连通分量的个数 for(i=1; i<=n; i++) { if(!vis[i]) { ans++; vis[i]=true; dfs(i); } } if(ans==1) //连通分量的个数为1,说明图是连通的 { dd=0; for(i=1; i<=n; i++ ) { if(odd[i]%2==1) //统计奇点的个数 dd++; } if( dd==0 ) //如果奇点的个数为0,则说明存在欧拉回路 printf("1\n"); else printf("0\n"); } else printf("0\n"); } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。