欧拉路径

参考https://www.cnblogs.com/wkfvawl/p/9626163.html https://www.cnblogs.com/Rorschach-XR/p/11795094.html

前言

学习本算法的机缘是昨天的杂题选讲里涵盖了一道\(noip\)模拟测试5的T1,然后我因为忘记欧拉回路的东西就全完了

定义

如果图G（有向图或者无向图）中所有边一次仅且一次行遍所有顶点的通路称作欧拉通路。
如果图G中所有边一次仅且一次行遍所有顶点的回路称作欧拉回路。
具有欧拉回路的图称为欧拉图（简称E图）。具有欧拉通路但不具有欧拉回路的图称为半欧拉图。
一次行遍所有顶点不代表每个顶点只能够经过一次

存在条件

无向图存在欧拉路径的条件:所有点度数都是偶数,或者仅有一对度数为奇数
有向图存在欧拉路径的条件:所有点入度等于出度,或者仅有一对点入度和出度差分别为+1,-1

求解方式

1.dfs求解
看见边就莽,不行就回溯,用栈记录经过点

void dfs(int x)
{
    for(int i=head[x];i;i=nxt[i])
    {
        if(vis[i])continue;
        int y=to[i];
        vis[i]=vis[i^1]=1;//The original edge_num should be 1.
        dfs(y);
    }
    st[++top]=x;
}

复杂度\(O(nm)\),虽然我觉得复杂度有点假
2.Fleury(佛罗莱)算法
改进了一点:没事不要走桥
其实我也不知道这叫不叫桥,就是其他未经过的路径
除非没有别的边,否则不去走桥
复杂度\(O(e^2)\)
3.Hierholzer算法
加入了当前弧优化

void dfs(int x)
{
    for(int i=head[x];i;i=nxt[i])
    {
        if(vis[i])continue;
        int y=to[i];
        vis[i]=vis[i^1]=1;//The original edge_num should be 1.
        head[x]=i;
        dfs(y);
        i=head[x];
    }
    st[++top]=x;
}

个人观点最后一种比较好打
复杂度\(O(n+m)\)

欧拉路径

原文：https://www.cnblogs.com/hzoi2018-xuefeng/p/12898612.html