admin 管理员组

文章数量: 1087580

欧拉回路（简单判断是否有欧拉回路存在）

题目大意：给出N个点，M条边，问有没有欧拉回路存在。

题目分析：1.无向图欧拉回路是否连通2.所有点的度为偶数。并查集+degree【】

代码：

#include<iostream>
#include<stdio.h>
#include<string.h>using namespace std;const int maxn=1000+10;
int degree[maxn];
int fa[maxn];int findset(int i)
{if(fa[i]==-1)return i;return fa[i]=findset(fa[i]);
}
void init()
{memset(fa,-1,sizeof(fa));memset(degree,0,sizeof(degree));
}
int main()
{int m,n;int u,v;int cnt;while(scanf("%d",&n)){cnt=0;if(n==0)break;init();scanf("%d",&m);for(int i=1;i<=m;i++){scanf("%d%d",&u,&v);//cout<<"***"<<endl;degree[u]++;degree[v]++;int pa=findset(u);int pb=findset(v);if(pa!=pb){fa[pa]=pb;}// cout<<"hahaha"<<endl;}/* for(int i=1;i<=n;i++){cout<<"fa[i]"<<"  "<<i<<"  "<<fa[i]<<endl;}*/for(int i=1;i<=n;i++){cout<<"findset(i)<<"<<findset(i)<<endl;cout<<"fa[i]<<"<<fa[i]<<endl;//这里运行一下，发现findset(i)跟fa[i]在起点处还是不同的。找祖先的话要用findsetif(findset(i)==i){cnt++;}}if(cnt>1){printf("0\n");continue;}// for(int i=1;i<=n;i++)//{//  cout<<degree[i]<<"degree[]"<<endl;//}cnt=0;//计数奇数度的点for(int i=1;i<=n;i++)if(degree[i]%2==1)cnt++;if(cnt!=0)printf("0\n");else printf("1\n");}return 0;
}

本文标签： 欧拉回路（简单判断是否有欧拉回路存在）

版权声明：本文标题：欧拉回路（简单判断是否有欧拉回路存在） 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1686635434a20012.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。