本文主要是介绍(((hdu3018连通分量的欧拉回路）），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目意思：
有一个团队的人要去逛小镇，这个镇是无向图，然后规定每条路只能走一次，且两个小镇之间只有一条小路。（就避免了多条路径的问题。）然后这个图有可能有连通分量，如果图有孤立点，那么这个点就忽略掉，（这个挺有用）。问要分为几组人马才能够把这个城市的小镇全部逛完。
解题思路：（连通分量，粗俗地讲就是一个图的几个隔离的子图，每个子图为一个连通分量）
这里有个公式：如果每个连通分量的节点的度为偶数，那么就可以一笔画，如果连通分量中的节点的度为奇数点个数除以2;由于题目的数据量有滴滴微大，节点数100000，边数200000；所以这里要用邻接表做，然后要算每一个连通分量，就要用到并查集了。
解题报告：
欧拉回路：图G，若存在一条路，经过G中每条边有且仅有一次，称这条路为欧拉路，如果存在一条回路经过G每条边有且仅有一次，
称这条回路为欧拉回路。具有欧拉回路的图成为欧拉图。
判断欧拉路是否存在的方法
有向图：图连通，有一个顶点出度大入度1，有一个顶点入度大出度1，其余都是出度=入度。
无向图：图连通，只有两个顶点是奇数度，其余都是偶数度的。
判断欧拉回路是否存在的方法
有向图：图连通，所有的顶点出度=入度。
无向图：图连通，所有顶点都是偶数度。
本题呢。先用并查集查看共有几棵树， 记录下每棵树中度为奇数的点的个数。 如果该树中度为奇数的点的个数为0， 且代表元的度为0，证明该点为孤立的点，按题目要求的略过就可以了。如果代表元的度不为0， 且该树中度为奇数的店为0，那么证明为欧拉回路，1组就能搞定；如果这两种情况都不属于，那么浏览该树中的点要用奇数点的个数/2
代码如下：
#include<stdio.h>
#include<string.h>
int pre[100006];
int degree[100006];
int map[100006],ans[100006],p[100006];
int find(int k)
{
if(k!=pre[k])
pre[k]=find(pre[k]);
return pre[k];
}
int main()
{
int m,n,i,k,h,aa,bb,root,r,sum;
while(scanf("%d%d",&m,&n)!=EOF)
{
for(i=1;i<=m;i++)
{
pre[i]=i;
degree[i]=0;
ans[i]=0;
p[i]=0;
}
for(i=1;i<=n;i++)
{
scanf("%d%d",&k,&h);
degree[k]++;
degree[h]++;
aa=find(k);
bb=find(h);
if(aa!=bb)
pre[aa]=bb;
}
r=0;
for(i=1;i<=m;i++)
{
root=find(i);
if(p[root]==0)
{
p[root]=1;
map[r]=root; // vt保存着集合，集合就是图
r++;
}
if(degree[i]%2==1)
ans[root]++; // 保存这个集合的奇数度数的个数
}
sum=0;
for(i=0;i<r;i++)-----------对图进行处理。。
{
if(degree[map[i]]==0) // 孤立点
continue;
if(ans[map[i]]==0) // 该集合是欧拉回路，有一条路
sum++;
else
sum=sum+(ans[map[i]]/2);//欧拉路径有s/2个；；
}
printf("%d\n",sum);
}
return 0;
}
这篇关于(((hdu3018连通分量的欧拉回路））的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
