DFSによるオイラーツアー順序を求める実装

高難度帯の部分問題として出てくるので実装を置いておく。

実装

以下の実装は、訪れた順に頂点を採番していく。

/// オイラーツアー
struct EulerianTrail{
  vector<int> order;
  
  EulerianTrail(vector<vector<int>>& G, int root=0){
    int n=G.size();
    order.resize(n);
    int cur=0;
    function<void(int,int)> dfs=[&](int v, int p){
      order[v]=cur;
      cur++;
      for(auto nv: G[v]){
        if(nv==p) continue;
        dfs(nv, v);
      }
    };
    dfs(root, -1);
  }
};