欧拉路径

    前提: 所有边联通
    有向图:
        (1) 路径: 要么所有点的出度等于入度，要么一个点入比出多一，一个出比入多一。
        (2) 回路: 入度和出度相同。
    前提: 所有边联通
    无向图:
        (1) 路径: 度数为奇数的点为 0 个或者 2 个。
        (2) 回路: 度数为奇数的点为 0 个。

欧拉路径输出 边

// 欧拉回路输出边
void dfs(int u){
    for(int &i = h[u];~i;){
        if(used[i]){
            i = ne[i];
            continue;
        }
        used[i] = true;
        if(type == 1) used[i ^ 1] = true;
        int t;
        if(type == 1){
            t = (i >> 1) + 1;
            if(i & 1) t = -t;
        }else t = i + 1;
        int j = e[i];
        i = ne[i];
        dfs(j);
        ans[cnt ++ ] = t;
    }
}

欧拉路径输出 点(最小字典序)

其实就是直接按最小搜

注意起点的选择，需要从度为奇数的点作为起点出发，否则随意选择一个度为偶数的点出发。

// 欧拉回路输出点 
int n, m;
int g[N][N];
int ans[N], cnt;
int d[N];

void dfs(int u){
    for(int i = 1;i <= n;i ++ ){
        if(g[u][i]){
            g[u][i] -- , g[i][u] -- ;
            dfs(i);
        }
    }

    ans[ ++ cnt] = u;
}

// 找到第一个度数不为 0 的点
int start = 1;
while(!d[start]) start ++ ;
// 找到第一个度数为奇数的点
for(int i = start;i <= n;i ++ ){
    if(d[i] & 1){
        start = i;
        break;
    }
}

dfs(start);