[数据结构与算法]欧拉路和欧拉回路

大前提：欧拉图都是联通的

以下定义摘自oi wiki

• 通过图中所有边恰好一次且行遍所有顶点的通路称为欧拉通路。

• 通过图中所有边恰好一次且行遍所有顶点的回路称为欧拉回路。

• 具有欧拉回路的无向图或有向图称为欧拉图。

• 具有欧拉通路但不具有欧拉回路的无向图或有向图称为半欧拉图。

• 非形式化地讲，欧拉图就是从任意一个点开始都可以一笔画完整个图，半欧拉图必须从某个点开始才能一笔画完整个图。

算法原理

• 要素：基于dfs的算法，去重是边判据，理由来自定义（可以直接删，也可以bool）
• 手段：对已知必然存在eular路的图，选定起点开始深搜，搜完所有的出边之后，压栈
• 倒序输出栈中元素（栈的fifo特性决定）

考虑一笔画的细节性质，eular图中必然存在环，且可能是环拼环
可能的删边操作：h[x]=nxt[i]，单链表直接删
注意无向图删边的同时也要去掉反边！（你可以开一个 bool used 来达成）

一，无向图的欧拉

欧拉路

• 充要条件：度数为奇数的点只有 0或者2个，其余的点度数为偶数

欧拉回路

• 充要条件：度数为奇数的点只有 0个，所有的点度数为偶数
• 特性：起点可以是所有点，从哪里都可以深搜

二，有向图的欧拉

欧拉路

• 充要条件：入度和出度不同的点只有 0或者2个，其余的点入度和出度相同
• 起点终点特性：起点入度比出度小1，终点入度比出度大1

欧拉回路

• 充要条件：入度和出度不同的点只有 0个，其余的点入度和出度相同

贴一个输出字典序最小的欧拉路径code

void eular(int x)
{
    for(int i=del[x];i<g[x].size();i=del[x])
    {
        del[x]=i+1;
        eular(g[x][i]);
    }
    ans.push(x);
}

int main()
{

    bool flag=1;
    int st=1;
    int cnt[2]={0,0};
    int a,b;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>a>>b;
        g[a].push_back(b);
        out[a]++; in[b]++;
    }

    for(int i=1;i<=n;i++)
    {
        sort(g[i].begin(),g[i].end());
        if(in[i]!=out[i])flag=0;
        if(in[i]-out[i]==1)cnt[1]++;
        if(out[i]-in[i]==1)cnt[0]++,st=i;
    }

    if(!flag&&!(cnt[0]==1&&cnt[1]==1))puts("No");
    else
    {
        eular(st);
        while(!ans.empty())
        {
            cout<<ans.top()<<" ";
            ans.pop();
        }
    }
}