src/tree/eulertour.hpp

View this file on GitHub
Last update: 2025-12-31 23:11:35+09:00
Include: #include "src/tree/eulertour.hpp"

Depends on

src/template.hpp

Code

#include "../template.hpp"

pair<vector<int>,vector<int>> ET(vector<vector<int>> G,int root=0){
    vector<int> in(si(G)),out(si(G));
    int now=0;
    auto dfs=[&](auto dfs,int v,int p) -> void {
        in[v]=now++;
        for(int e: G[v])
            if(e!=p) dfs(dfs,e,v);
        out[v]=now++;
    };
    dfs(dfs,root,-1);
    return make_pair(in,out);
}

pair<vector<int>,vector<int>> vtetv(vector<pair<int,int>> es,int root=0){
    int N=si(es)+1;
    vector<vector<pair<int,int>>> G(N);
    rep(i,N-1) G[es[i].fi].emplace_back(es[i].se,i),G[es[i].se].emplace_back(es[i].fi,i);
    vector<int> etv(N-1);
    vector<int> vte(N);
    auto dfs=[&](auto dfs,int v,int p) -> void {
        for(auto [e,id]: G[v]){
            if(e==p) continue;
            dfs(dfs,e,v);
            vte[e]=id;
            etv[id]=e;
        }
    };
    dfs(dfs,root,-1);
    return make_pair(vte,etv);
}

#line 2 "src/template.hpp"
#include <bits/stdc++.h>
using namespace std;
#define si(a) (long)a.size()
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(int)(n);++i)
template<typename S,typename F> bool chmin(S&a,F b){return b<a?(a=b,1):0;}
template<typename S,typename F> bool chmax(S&a,F b){return b>a?(a=b,1):0;}
bool _=(ios::sync_with_stdio(0),cin.tie(0),cout<<fixed<<setprecision(16),0);
#line 2 "src/tree/eulertour.hpp"

pair<vector<int>,vector<int>> ET(vector<vector<int>> G,int root=0){
    vector<int> in(si(G)),out(si(G));
    int now=0;
    auto dfs=[&](auto dfs,int v,int p) -> void {
        in[v]=now++;
        for(int e: G[v])
            if(e!=p) dfs(dfs,e,v);
        out[v]=now++;
    };
    dfs(dfs,root,-1);
    return make_pair(in,out);
}

pair<vector<int>,vector<int>> vtetv(vector<pair<int,int>> es,int root=0){
    int N=si(es)+1;
    vector<vector<pair<int,int>>> G(N);
    rep(i,N-1) G[es[i].fi].emplace_back(es[i].se,i),G[es[i].se].emplace_back(es[i].fi,i);
    vector<int> etv(N-1);
    vector<int> vte(N);
    auto dfs=[&](auto dfs,int v,int p) -> void {
        for(auto [e,id]: G[v]){
            if(e==p) continue;
            dfs(dfs,e,v);
            vte[e]=id;
            etv[id]=e;
        }
    };
    dfs(dfs,root,-1);
    return make_pair(vte,etv);
}