欧拉回路（简单判断是否有欧拉回路存在）
发布时间
阅读量：
阅读量
https://cn.vjudge.net/contest/209173#problem/N
题目大意：给出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]在起点处还是不同的。找祖先的话要用findset
if(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;
}
AI写代码全部评论 (0)
还没有任何评论哟~