欧拉序与DFS序

@[TOC]
欧拉序与DFS序相似又不同

欧拉序的定义
树在dfs过程中的节点访问顺序称为欧拉序.
那有人会问：dfs序和欧拉序啥区别？

dfs序：是指将一棵树被dfs时所经过的节点顺序（不绕回原点）。
欧拉序：就是从根结点出发，按dfs的顺序在绕回原点所经过所有点的顺序。

欧拉序与dfs序不同地方在于，欧拉序中每个节点可以出现多次，比如进入一次退出一次，又比如每次回溯时记录一次。
代码：

s[maxn]存放“入时间戳”，e[maxn]存放“出时间戳”；

DFS序

核心代码

const int maxn = 1e5+5;
vector<int> g[maxn]; //存放节点
int s[maxn], e[maxn];//s[maxn]存放“入时间戳”，e[maxn]存放“出时间戳”；
int n,id,len;
int dfsxu[20000];//存放dfs序

void dfs(int u, int fa) {
    s[u] = ++id;
    dfsxu[++len]=u;
    for(int i = 0; i < g[u].size(); ++i) {
        int v = g[u][i];
        if(v == fa) continue;
        dfs(v, u);
    }
    e[u] = id;
}

vector<int> g[maxn]; //存放节点
int s[maxn], e[maxn];//s[maxn]存放“入时间戳”，e[maxn]存放“出时间戳”；
int dfsxu[20000];//存放dfs序
完整代码</int>

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
vector<int> g[maxn]; //存放节点
int s[maxn], e[maxn];//s[maxn]存放“入时间戳”，e[maxn]存放“出时间戳”；
int n,id,len;
int dfsxu[20000];//存放dfs序

void dfs(int u, int fa) {
    s[u] = ++id;
    dfsxu[++len]=u;
    for(int i = 0; i < g[u].size(); ++i) {
        int v = g[u][i];
        if(v == fa) continue;
        dfs(v, u);
    }
    e[u] = id;
}
int main() {
    memset(s,0,sizeof(s));
    memset(e,0,sizeof(e));
    memset(dfsxu,0,sizeof(dfsxu));
    ios::sync_with_stdio(0);
    cin >> n;
    for(int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    id = 0;
    dfs(1, -1);
    cout<<"DFS序:";
    for(int i=1;s[i]!=0;i++)
    {
        cout<<dfsxu[i];
    }
    cout<<endl;
    cout<<"入时间戳:";
    for(int i=1;s[i]!=0;i++)
    {
        cout<<s[i];
    }
    cout<<endl;
    cout<<"出时间戳:";
    for(int i=1;e[i]!=0;i++)
    {
        cout<<e[i];
    }
    cout<<endl;

    return 0;
}

欧拉序

vector<int> g[40010]; //存放节点
int oulaxu[80020]; //存放欧拉序在，在欧拉序中第一次出现为“入时间戳”，第二次出现为“出时间戳”。
核心代码</int>

vector<int> g[40010]; //存放节点
int oulaxu[80020]; //存放欧拉序在，在欧拉序中第一次出现为“入时间戳”，第二次出现为“出时间戳”。
int len;

void dfs(int u,int fa)
{
    oulaxu[++len]=u;
    int sz=g[u].size();
    for(int i=0; i<sz; i++)
    {
        if(g[u][i]!=fa)
            dfs(g[u][i],u);
        }

    oulaxu[++len]=u;
}

vector<int> g[40010]; //存放节点
int oulaxu[80020]; //存放欧拉序在，在欧拉序中第一次出现为“入时间戳”，第二次出现为“出时间戳”。
完整代码</int>

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

vector<int> g[40010]; //存放节点
int oulaxu[80020]; //存放欧拉序在，在欧拉序中第一次出现为“入时间戳”，第二次出现为“出时间戳”。
int len;

void dfs(int u,int fa)
{
    oulaxu[++len]=u;
    int sz=g[u].size();
    for(int i=0; i<sz; i++)
    {
        if(g[u][i]!=fa)
            dfs(g[u][i],u);
        }

    oulaxu[++len]=u;
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        len=0;
        memset(oulaxu,0,sizeof(oulaxu));
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
        {
            g[i].clear();
        }
        for(int i=1; i<=n-1; i++)
        {
            int from,to;
            scanf("%d%d",&from,&to);
            g[from].push_back(to);
            g[to].push_back(from);
        }
        dfs(1,0);
        for(int i=1;i<=len;i++)
        {
            printf("%d ",oulaxu[i]);
        }
    }

}