图的类型与性质——欧拉图、（竞赛图、哈密顿图）

一、欧拉图：
无向图连通性的小问题——欧拉路问题，俗称一笔画问题。

给定一张无向图，若存在一条从节点S到节点T的路径，恰好不重不漏的经过每条边一次（可以重复经过图中的顶点），则称该路径为S到T的欧拉路。

特别的，若存在一条从节点S出发的路径，敲好不重不漏的经过每条边一次（可以重复经过图中的节点），最终回到起点S，则称该路径为欧拉回路。存在欧拉回路的无向图被称为欧拉图。

欧拉图的判定：
一张无向图为欧拉图，当且仅当无向图连通，并且每个点的度数都是偶数。

欧拉路的存在性判定：
一张无向图中存在欧拉回路，当且仅当无向图连通，并且图中恰好有两个节点的度数为奇数，其他节点的度数都是偶数。这两个度数为奇数的节点就是欧拉路的起点S和终点T。

在判定无向图存在欧拉回路之后，我们可以借助深度优先遍历和栈，求出欧拉回路的一种具体方案。//回溯时入队。

欧拉图每个节点度数为偶数的说明：
只要到达一个节点，就必定有一条尚未走过的边可以离开该点。

假设我们采用邻接表存储无向图，我们可以在访问一条边（x，y）后，即使修改表头head（x），令它指向下一条边。这样我们每次只需取出head（x），就自然跳过了所有以访问过的边。
另外，因为欧拉回路DFS的递归层数时O(m)级别，容易造成系统栈溢出。我们可以用另一个栈，模拟机器的递归过程，把代码转化为非递归实现。
时间复杂度为O（n+m）。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<vector>
#define ll long long
using namespace std;
const int maxn=100010;
int head[maxn],ver[maxn],nt[maxn],tot;
int st[maxn],ans[maxn];
bool vis[maxn];
int n,m,top,t;

void add(int x,int y)
{
    ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
}

void euler(void)
{
    st[++top]=1;
    while(top>0)
    {
        int x=st[top],i=head[x];
        while(i&&vis[i]) i=nt[i];

        if(i)
        {
            st[++top]=ver[i];
            vis[i]=vis[i^1]=true;
            head[x]=nt[i];
        }
        else
        {
            top--;
            ans[++t]=x;
        }
    }
}

int main(void)
{
    cin>>n>>m;
    tot=1;

    int x,y;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    euler();
    for(int i=t;i;i--) printf("%d\n",ans[i]);

    return 0;
}

例题：POJ2230 Watchcow：
题意：给定N各点，M条边的无向图（1≤N≤10⁴,1≤M≤5*10⁴)，求一条路径，从节点1出发，最后回到节点1，并且满足每条边恰好被沿着正反两个方向分别经过一次。若有多种方案，输出任意一种即可。
我们只需要在求欧拉回路的参考程序中，去掉对每条边的vis标记，即可得到本题的解答。这是因为，按照一般的存储方式，每条无向边在邻接链表中会以正反两个方向分别保存一次。若没有vis标记，则根据表头数组head的更新方法，每条无向边会被正，反两个方向各经过一次，恰好符合题目要求。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<vector>
#define ll long long
using namespace std;
const int maxn=100010;
int head[maxn],ver[maxn],nt[maxn],tot;
int st[maxn],ans[maxn];
int n,m,top,t;

void add(int x,int y)
{
    ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
}

void euler(void)
{
    st[++top]=1;
    while(top>0)
    {
        int x=st[top],i=head[x];

        if(i)
        {
            st[++top]=ver[i];
            head[x]=nt[i];
           // printf("%d***\n",ver[i]);
        }
        else
        {
            top--;
           // printf("%d**\n",x);
            ans[++t]=x;
        }
    }
}

int main(void)
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        tot=1;top=0;t=0;
        for(int i=1;i<=n;i++)
            head[i]=0;
        int x,y;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&x,&y);
            add(x,y);
            add(y,x);
        }
        euler();
        for(int i=t;i;i--) printf("%d\n",ans[i]);

    }

    return 0;
}