DFS 无向图欧拉路径

欧拉通路: 通过图中每条边且只通过一次，并且经过每一顶点的通路。
欧拉回路: 通过图中每条边且只通过一次，并且经过每一顶点，最终能够回到起点。
定理1： 含有至少2个顶点的连通多重图具有欧拉回路当且仅当它的每个顶点的度都是偶数。
定理2： 连通多重图具有欧拉通路但无欧拉回路当且仅当它恰有2个度为奇数的顶点。

欧拉回路算法核心思想
(1) 从G中任选的顶点开始，连续的加入边形成回到该顶点的回路
(2) 删除这个回路的边之后G为H
(3) 在H中重复(1)(2)过程，直到H中没有边。

无向图
(1) 判断是否存在欧拉路径，如果不存在，算法结束
(2) 如果存在欧拉通路，从度为奇数的点开始BFS; 如果存在欧拉回路，从任意结点开始
(3) 设DFS到点u, 遍历u 的出边e(u, v)
(4) 如果e未被删除，跳转到(5), 否则跳转到(3)
(5) 删除e(u, v)以及它的反向边, DFS点v
(6) 存储u

有向图
(1) 判断是否存在欧拉路径，如果不存在，算法结束
(2) 如果存在欧拉通路，从入度比出度小1的结点开始BFS;如果存在欧拉回路，从任意结点开始
(3) 设DFS到点u, 遍历u的出边e(u, v)
(4) 如果e未被删除，跳转到(5), 否则跳转到(3)
(5) 删除e(u, v), DFS点v
(6) 存储u

求无向图欧拉路径代码
#include
#include

const int MAXN = 100 + 2;
bool g[MAXN][MAXN];
int degree[MAXN];
int n, e; // vertex number, edge number

void dfs_euler(int s, std::vector& vec)
{
    for (int i = 1; i <= n; ++i)
        if (g[s][i])
        {
            g[s][i] = g[i][s] = false;// 删除这个条边
            dfs_euler(i, vec);        // 从任意与它相连的结点继续搜索
        }
    vec.push_back(s);
}

int main()
{
    std::cin >> n >> e;
    int u, v;
    while (e--)
    {
        std::cin >> u >> v;
        g[u][v] = g[v][u] = true;
        ++degree[u];       // 统计结点的度
        ++degree[v];
    }

    // 如果存在度为奇数的结点，则为欧拉通路，应从奇点开始；欧拉回路可以从任意结点开始
    int s = 1;
    int cnt = 0; // 统计度为奇数的结点个数
    for (int i = 1; i <= n; ++i)
        if (degree[i] % 2)
        {
            s = i;
            ++cnt;
        }

    if (n >= 2 && (cnt == 2 || cnt == 0))
    {
        std::vector ans;
        dfs_euler(s, ans);
        for (unsigned int i = 0; i < ans.size(); ++i)
            std::cout << ans[i] << "   ";
        std::cout << std::endl;
    }
    else
        std::cout << "No circuit" << std::endl;

    return 0;
}

5 5
1 2
2 3
3 4
4 5
5 1
1   5   4   3   2   1