算法学习之路|欧拉回路初见
欧拉道路，一个词概括就是一笔画。一张连通图能用一笔画不重复的走完每一条边的就是欧拉道路，起点和终点是同一点的是欧拉回路。
那么判断一张图是不是欧拉回路就可以通过记录每一点的度数，所有点度数均是偶数的是欧拉回路，有一到两个点度数是奇数的是欧拉道路，有两个点以上是奇数度数的不是欧拉道路。有向图条件更苛刻一点，需要点入度和出度相等才能构成欧拉回路，即使是欧拉道路也需要入度和出度相差仅为一，且这样的店不能超过两个。
七桥问题，给出一张图，判断是否是欧拉回路:
#include <iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int index[1005],du[1005];
int Find(int x)//并查集
{
if(x==index[x])
return x;
else
return index[x]=Find(index[x]);//回溯直到找到根节点
}
void meet(int x,int y)
{
int f1=Find(x);
int f2=Find(y);
if(f1!=f2)
index[f1]=f2;
}//已经连接的两个集合并入一个根节点，压缩路径
int main()
{
int N,M,a,b;
while(scanf("%d",&N)&&N)
{
for(int i=1;i<=N;i++)
index[i]=i;//并查集初始化
memset(du,0,sizeof(du));
scanf("%d",&M);
while(M--)
{
scanf("%d %d",&a,&b);
du[a]++;
du[b]++;//记录该点的度,无向图不区分入度出度
meet(a,b);
}
int flag=0;//记录并查集有个数（根节点）
for(int i=1;i<=N;i++) { if(Find(i)==i) flag++; } if(flag>1)//非连通图不能形成欧拉回路
printf("0\n");
else
{
flag=0;
for(int i=1;i<=N;i++)
if(du[i]%2)//判断点的度数奇偶性
{
flag=1;
break;
}
if(flag)
printf("0\n");
else
printf("1\n");
}
}
return 0;
}代码是照着模板敲的，用到了并查集，回顾了一下。
并查集用来判断两个节点是否同属于一个根节点，在这里用来判断图是否是连通图。
并查集把已经确定相互连接的两个集合并入一个集合，
此题只需判断是否欧拉回路，所以不必深究具体的道路，如果是求欧拉道路，判断点的度数使只需加上奇数不超过两个。