【图论】欧拉图

欧拉回路Eulerian Cycle：通过图中每条边恰好一次的回路
欧拉通路Eulerian Path：通过图中每条边恰好一次的通路
欧拉图：具有欧拉回路的图
半欧拉图：具有欧拉通路但不具有欧拉回路的图

欧拉图中所有顶点的度数都是偶数。
若 G 是欧拉图，则它为若干个环的并，且每条边被包含在奇数个环内。

判别法

无向图是欧拉图当且仅当：
非零度顶点是连通的
顶点的度数都是偶数
这个条件很容易满足。

无向图是半欧拉图当且仅当：
非零度顶点是连通的
恰有2个奇度顶点
这个条件很容易满足。

有向图是欧拉图当且仅当：
非零度顶点是强连通的
每个顶点的入度和出度相等
（强连通 = 从同一个强连通的每个点出发都能到达分量上的所有点）

有向图是半欧拉图当且仅当：
非零度顶点是弱连通的
至多一个顶点的出度与入度之差为1
至多一个顶点的入度与出度之差为1
其他顶点的入度和出度相等

关于零度顶点连通与否，是否属于欧拉图的问题，看每个问题具体的定义。

Hierholzer 算法

过程
算法流程为从一条回路开始，每次任取一条目前回路中的点，将其替换为一条简单回路，以此寻找到一条欧拉回路。如果从路开始的话，就可以寻找到一条欧拉路。(或者先把缺失的那条边补上，找到一个欧拉回路，再从缺失的边那里剪开，即可。）首先要确定要求的欧拉回路或者欧拉通路存在，如果是欧拉回路存在可以从任何点开始dfs，如果只有欧拉通路存在，则要在无向图的奇数度数点开始dfs，有向图在唯一的出度比入度大1的点开始dfs。dfs完成后栈中的元素逆序就是一条欧拉回路/欧拉通路。为了保证复杂度，要在算法的过程中跳过已经遍历过的边，这个问题是这个算法最让人头疼的地方，最简单的方式是使用set，但是会涉及到在for迭代中删除set中元素的问题。

这里一般用set来存图，然后实现删边，从而使得算法的复杂度为 \(O(m\log{m})\) ，注意，stl中提供erase的容器，返回值为删除之后的下一个迭代器。也就是说，如果删除成功，则直接用erase的返回值就可以继续循环，否则直接迭代器++即可。

这个是C++ 11的标准写法：

for (auto it = my_set.begin(); it != my_set.end(); ) {
    if (some_condition) {
        it = numbers.erase(it);
    } else {
        ++it;
    }
}

对于有向图，下面的算法是有效的（仅限无平行边的简单情况，不推荐）：

set<int> G[MAXN];
stack<int> stk;
 
void dfs (int u) {
    for (auto it = G[u].begin(); it != G[u].end(); ) {
        int v = *it;
        it = G[u].erase(it);
        dfs(v);
    }
    stk.push (u);
}

先判断欧拉通路存在（最多只有一对节点入度和出度不相等，并且一个是大一一个是小一）。只需要在出度唯一比入度大1的节点开始dfs，或者如果没有这样的节点，从任意节点开始dfs，然后把stk中的节点逆序输出，如果stk中的节点数量恰好等于边数+1，则欧拉通路/欧拉回路已经被找到，否则此图不连通，无解。

但是如果是无向图，这个算法要删除别的地方的set循环中的迭代器，又引入了新的不确定。

从luogu https://www.luogu.com.cn/article/kv9n9167 这篇文章学到了一个很好的方式。

使用链式前向星的方法存图，相邻的边要同时加入。然后每个节点维护一个链表的头节点，当在dfs到u，然后删除u中指向v的边时，容易知道v一定是此时链表的头节点，此时把头节点向前移动1，如果下一次再遇到u节点则不会再遍历同一个头。同时将(u,v)这一条边打上已被使用的标记。当遍历节点v时，如果遇到了指向u的那条边（反向边），那么检查这个反向边是否已经被遍历，如果是的话则继续移动头节点。这个也是链式前向星写法无法被vector写法替代的一个地方。

namespace EulerianPath {
int n;
struct Edge {
    int u;
    int v;
    int next;
};
vector<Edge> edge;
vector<int> head;

void Init (int _n) {
    n = _n;
    edge.clear();
    edge.push_back ({0, 0, 0});
    head.clear();
    head.resize (n + 1);
}

void AddDirectedEdge (int u, int v) {
    Edge e = {u, v, head[u]};
    head[u] = (int) edge.size();
    edge.push_back (e);
}

int HaveEulerianCycle() {
    vector<int> outdeg (n + 1);
    vector<int> indeg (n + 1);
    for (auto [u, v, next] : edge) {
        ++outdeg[u];
        ++indeg[v];
    }
    for (int i = 1; i <= n; ++i) {
        if (outdeg[i] != indeg[i]) {
            return -1;
        }
    }
    // 如果连通
    return 1;
}

int HaveEulerianPath() {
    vector<int> outdeg (n + 1);
    vector<int> indeg (n + 1);
    for (auto [u, v, next] : edge) {
        ++outdeg[u];
        ++indeg[v];
    }
    int inV = 0, outV = 0;
    for (int i = 1; i <= n; ++i) {
        if (outdeg[i] == indeg[i]) {
            continue;
        }
        if (outdeg[i] > indeg[i]) {
            if (outV == 0) {
                outV = i;
            } else {
                return -1;
            }
        } else {
            if (inV == 0) {
                inV = i;
            } else {
                return -1;
            }
        }
    }
    // 如果连通
    return outV ? outV : 1;
}

vector<int> FindEulerCyclerOrPath() {
    int S = HaveEulerianPath();
    if (S == -1) {
        return {};
    }
    vector<int> stk;
    auto dfs = [&] (auto self, int u) {
        for (int &i = head[u]; i;) {
            auto [_u, v, next] = edge[i];
            i = next;
            dfs (v);
        }
        stk.push (u);
    }
    if (stk.size() == edge.size()) {
        // 因为edge有一条编号为0的虚拟边，所以大小刚好相等
        reverse (stk.begin(), stk.end());
        return stk;
    }
    return {};
}

}

上述算法未经验证