『算法-ACM 竞赛-图论』-欧拉图-欧拉回路-Euler-Fluery-Hierholzer-逐步插入回路法-DFS 详解-并查集

图论-欧拉图-欧拉回路-Euler-Fluery-Hierholzer-逐步插入回路法-DFS 详解-并查集

欧拉图性质：

1.无向连通图 G 是欧拉图，当且仅当 G 不含奇数度结点(G 的所有结点度数为偶数)；

2.无向连通图G 含有欧拉通路，当且仅当 G 有零个或两个奇数度的结点；

3.有向连通图 D 是欧拉图，当且仅当该图为连通图且 D 中每个结点的入度=出度；

4.有向连通图 D 含有欧拉通路，当且仅当该图为连通图且 D 中除两个结点外，其余每个结点的入度=出度，且此两点满足 deg－(u)－deg+(v)=±1。（起始点 s 的入度=出度-1，结束点 t 的出度=入度-1 或两个点的入度=出度）；

对于欧拉图问题，有如下解决问题的方法：

1.Eular 算法（欧拉算法），欧拉问题最标准的算法。

2.Fluery 算法（佛罗莱算法），欧拉问题最广泛的算法

3.Hierholzer (希霍尔泽算法应该是这么翻译）又叫逐步插入回路法，高效的算法。

4.DFS 算法，暴力无脑解题算法，虽然 Fluery，Euler 也是递归实现。这个我看看又看了看，确实跟 Euler 没区别，跟 Hierholzer 也没区别

5.并查集算法，网络流解混合图的时候可以使用。https://blog.csdn.net/liyanfeng1996/article/details/52767039

以上是网上的各种说法的总结，也就是只有这 3 种做法，暴力的搜索（1，3，4）

1.对于第一种方法只要有欧拉路径或者欧拉回路，就可以使用，应该是可以用于无向图的，不过使用前需要判断节点的度，是否存在，复杂度有点高，也不用避免隔什么的感觉跟 DFS 很像，简单的题暴力就完事了。

就是暴力，能走就走，不能走就不走，然后从小号到最大号遍历，也就保证了路径的序号为字典序最小的情况。

模板：

int g[510][510];
stack<int> s;
int d[510];
void euler(int u)
{
    for(int v=1; v<=500; v++)
    {
        if(g[u][v])
        {
            g[u][v]--;
            g[v][u]--;
            euler(v);
            s.push(v);
        }
    }
}
int main()
{
    int u,v;
    int n;
    cin>>n>>m;// 点，边
    for(int i=1; i<=m; i++)
    {
        cin>>u>>v;
        g[u][v]++;
        g[v][u]++;
        d[u]++;
        d[v]++;
    }
    int flag=1;
    int cnt=0;
    for(int i=n; i>=1; i--)
        if(d[i]%2)
        {
            flag=i;
            cnt++;
        }
    if(cnt>2)
    {
        cout<<"No Euler"<<endl;
        return 0;
    }
    euler(flag);
    s.push(flag);
    while(!s.empty())
    {
        cout<<s.top()<<endl;
        s.pop();
    }
}




void fleury(int s){
    bool flag;
    st.push(s);
    while(!st.empty()){
        flag = 0;
        for(int i = 1; i <= n; i++){
            if(edge[st.top()][i] > 0){
                flag = 1; break;
            }
        }
        if(flag){
            int x = st.top();
            st.pop();
            dfs(x);
        }
        else{
            printf("%d ",st.top());
            st.pop();
        }

    }