无向图欧拉路径输出字典序最小的一条路径模板题

求欧拉回路的模板

求最小字典序的方法

先遍历1号点（编号从1到n），则1号点一定最后被加入欧拉路径。
因此只要按照从小到大的点的序号搜，就可以得到字典序最小的欧拉路径（最后逆序输出，最小的点会最后加入ans)

所以开始时优先搜索序号较小的点

无向图求欧拉路径

C++代码

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510;

int n = 500, m;
//邻接矩阵存图
int g[N][N];
int ans[1100], cnt;
int d[N];

void dfs(int u)
{   
    //因为最后的欧拉路径的序列是ans数组逆序，
    //节点u只有在遍历完所有边之后最后才会加到ans数组里面，所以逆序过来就是最小的字典序
    for (int i = 1; i <= n; i ++ )
        if (g[u][i])
        {
            //删边优化
            g[u][i] --, g[i][u] -- ;
            dfs(i);
        }
    ans[ ++ cnt] = u;
}

int main()
{
    cin >> m;
    while (m -- )
    {
        int a, b;
        cin >> a >> b;
        g[a][b] ++, g[b][a] ++ ;
        d[a] ++, d[b] ++ ;
    }

    int start = 1;
    while (!d[start]) ++start; // 较小编号作为起点
    //数据保证有解一定存在欧拉回路,那么让第一条度数为奇数的点作为起点
    for (int i = 1; i <= 500; ++i) {
        if (d[i] % 2) { // 奇数点作为起点
            start = i;
            break;
        }
    }

    dfs(start);


    for (int i = cnt; i; i -- ) printf("%d\n", ans[i]);

    return 0;
}