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

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

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

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

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

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

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

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