Fleury算法计算欧拉图路径

6.11集训队选拔赛有道欧拉图的题，没带模板就尝试去写没写出来。因为在acm里欧拉图的题可以说是少之又少，就算是我现在想要去复习一编，然而连题目都找不到几个。就算有欧拉图的题目，也只是考察他的性质（欧拉图的判定啊什么的）

阅读之前请读者自备图论相关常识

Fleury算法是一种解决欧拉图的常见算法，它的核心思想在于我在进欧拉路径的时候，尽量去走非桥边。其实这是很显然的，因为当你在走过了一个桥边，原图将被分为两个子图，如果之前还有边未走完，那么我将无法回到原子图上，也就无法形成欧拉路径了。

优先走非桥边，这是一个非常必要的前提条件，而事实证明，这也是一个充分条件。
以下是我整理的个人模板

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;

const int maxn = 110;

int stk[maxn], ans[maxn], degree[maxn];
int top, atop;
int n, m, st, num;
bool go[maxn][maxn];

void dfs(int u)
{
    stk[top++] = u;
    for (int i = 1; i <= n; ++i) {
        if (go[u][i]) {
            go[u][i] = go[i][u] = 0;
            degree[i]--;
            degree[u]--;
            dfs(i);
            break;
        }
    }
}

void fleury(int st)
{
    top = atop = 0;
    stk[top++] = st;
    while (top > 0) {
        if (degree[stk[top - 1]])
            dfs(stk[--top]);
        else
            ans[atop++] = stk[--top]; //bridge
    }
    while (atop > 1)
        printf("%d ", ans[--atop]);
    printf("%d\n", ans[0]);
}

inline void init()
{
    memset(go, false, sizeof go);
    memset(degree, 0, sizeof degree);
    st = num = 0;
}

int main()
{
    int u, v;
    while (scanf("%d %d", &n, &m) != EOF) {
        init();
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &u, &v);
            go[u][v] = go[v][u] = true;
            degree[u]++;
            degree[v]++;
        }
        for (int i = 1; i <= n; i++)
            if (degree[i] & 1) {
                num++;
                st = st ? st : i;
            }
        if (num == 0)
            fleury(1);
        else if (num == 2)
            fleury(st);
        else
            puts("No Euler Path!");
    }
    return 0;
}