【题目来源】
https://oj.czos.cn/p/2052

【题目描述】
一个有 n 个结点的无向连通图，这些结点以编号 1，2，...，n 进行编号，现给出结点间的连接关系。
请以结点 1 为起点，按 dfs（深度优先搜索）、优先访问小编号结点的顺序遍历并输出该图。

【输入格式】
第一行为两整数，n 和 e，表示 n 个顶点，e 条边。（2≤n,e≤10）
以下 e 行每行两个数，表示两个结点是连通的。

【输出格式】
只有一行，为按照优先访问小编号结点的 dfs 的结果。​​​​​​​

【输入样例】
5 7
1 2
1 3
1 4
2 4
2 5
3 5
4 5​​​​​​​

【输出样例】
1 2 4 5 3

【数据范围】
2≤n,e≤10

【算法分析】
● 本题是一道“图的 dfs 遍历”的题目，虽然给出了其代码。但我求解此题的目的是在深度优先搜索（DFS）的代码基础上引出 DFS 序和欧拉序的代码。

● DFS 序和欧拉序是树结构序列化最常用的两种方法。它们在树上莫队、树链剖分、子树统计等问题中经常出现。

● DFS 序和欧拉序的代码，与 DFS（深度优先搜索） 的代码差别不大。
（1）求解本题的 DFS 序代码（相比于深度优先搜索代码引入了时间戳数组 ts[] 及变量 idx）

#include <bits/stdc++.h>
using namespace std;

const int N=15;
vector<int> g[N];
bool st[N];
int n,m;
int ts[N],idx;

void dfs(int u,int fa) {
    ts[u]=++idx; //timestamp
    st[u]=true;
    for(int i=0; i<g[u].size(); i++) {
        int t=g[u][i];
        if(!st[t]) dfs(t,u);
    }
}

int main() {
    cin>>n>>m;
    while(m--) {
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    for(int i=1; i<=n; i++) {
        sort(g[i].begin(),g[i].end());
    }

    dfs(1,-1);

    for(int i=1; i<=n; i++) {
        cout<<"ts["<<i<<"]="<<ts[i]<<endl;
    }

    return 0;
}

/*
in:
5 7
1 2
1 3
1 4
2 4
2 5
3 5
4 5

out:
ts[1]=1
ts[2]=2
ts[3]=5
ts[4]=3
ts[5]=4
*/

（2）求解本题的欧拉序代码（相比于深度优先搜索代码引入了 euler[]、in[]、out[] 数组及变量 idx）
euler[]：存储完整的长度为 2n 的欧拉序列（本体）
in[]：记录每个节点的入栈位置（用于确定区间左/右端点）
out[]：记录每个节点的出栈位置（非祖孙路径时左端点用 out[u]）

#include <bits/stdc++.h>
using namespace std;

const int N=15;
//Euler tour array, length=2n
int euler[N<<1];
int in[N],out[N];

vector<int> g[N];
bool st[N];
int n,m;
int idx;

void ola(int u,int fa) {
    euler[++idx]=u; //record on entry
    in[u]=idx; //entry timestamp
    st[u]=true;
    for(int i=0; i<g[u].size(); i++) {
        int t=g[u][i];
        if(!st[t]) ola(t,u);
    }
    euler[++idx]=u; //record on exit
    out[u]=idx; //exit timestamp
}

int main() {
    cin>>n>>m;
    while(m--) {
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    for(int i=1; i<=n; i++) {
        sort(g[i].begin(),g[i].end());
    }

    ola(1,-1);

    for(int i=1; i<=2*n; i++) {
        cout<<euler[i]<<" ";
    }

    return 0;
}

/*
in:
5 7
1 2
1 3
1 4
2 4
2 5
3 5
4 5

out:
1 2 4 5 3 3 5 4 2 1
*/

基于本题样例，其欧拉序的求解过程如下所示：

基于本题样例，邻接表排序后：
g[1] = [2, 3, 4]
g[2] = [1, 4, 5]
g[3] = [1, 5]
g[4] = [1, 2, 5]
g[5] = [2, 3, 4]


基于上述邻接表，本题欧拉序求解过程如下所示：
----------------------------------------------------------------------------------
步骤    当前节点    操作    欧拉序                            栈状态
1       1           入栈    [1]                               [1]
2       1→2         入栈    [1, 2]                            [1, 2]
3       2→4         入栈    [1, 2, 4]                         [1, 2, 4]
4       4→5         入栈    [1, 2, 4, 5]                      [1, 2, 4, 5]
5       5→3         入栈    [1, 2, 4, 5, 3]                   [1, 2, 4, 5, 3]
6       3           出栈    [1, 2, 4, 5, 3, 3]                [1, 2, 4, 5]
7       5           出栈    [1, 2, 4, 5, 3, 3, 5]             [1, 2, 4]
8       4           出栈    [1, 2, 4, 5, 3, 3, 5, 4]          [1, 2]
9       2           出栈    [1, 2, 4, 5, 3, 3, 5, 4, 2]       [1]
10      1           出栈    [1, 2, 4, 5, 3, 3, 5, 4, 2, 1]    []
----------------------------------------------------------------------------------

【算法代码】

#include <bits/stdc++.h>
using namespace std;

const int N=15;
vector<int> g[N];
bool st[N];
int n,m;

void dfs(int u,int fa) {
    cout<<u<<" ";
    st[u]=true;
    for(int i=0; i<g[u].size(); i++) {
        int t=g[u][i];
        if(!st[t]) dfs(t,u);
    }
}

int main() {
    cin>>n>>m;
    while(m--) {
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    for(int i=1; i<=n; i++) {
        sort(g[i].begin(),g[i].end());
    }

    dfs(1,-1);

    return 0;
}

/*
in:
5 7
1 2
1 3
1 4
2 4
2 5
3 5
4 5

out:
1 2 4 5 3
*/

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/139681246