算法学习之路|欧拉回路初见

欧拉道路，一个词概括就是一笔画。一张连通图能用一笔画不重复的走完每一条边的就是欧拉道路，起点和终点是同一点的是欧拉回路。

那么判断一张图是不是欧拉回路就可以通过记录每一点的度数，所有点度数均是偶数的是欧拉回路，有一到两个点度数是奇数的是欧拉道路，有两个点以上是奇数度数的不是欧拉道路。有向图条件更苛刻一点，需要点入度和出度相等才能构成欧拉回路，即使是欧拉道路也需要入度和出度相差仅为一，且这样的店不能超过两个。

七桥问题，给出一张图，判断是否是欧拉回路:

#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;
}

代码是照着模板敲的，用到了并查集，回顾了一下。

并查集用来判断两个节点是否同属于一个根节点，在这里用来判断图是否是连通图。

并查集把已经确定相互连接的两个集合并入一个集合，

此题只需判断是否欧拉回路，所以不必深究具体的道路，如果是求欧拉道路，判断点的度数使只需加上奇数不超过两个。