tree/euler_tour.hpp

• View this file on GitHub
• Last update: 2024-02-15 01:16:17+09:00
• Include: #include "tree/euler_tour.hpp"

Code

 #pragma once

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


/// オイラーツアー
struct EulerTour{
  vector<int> order;
  vector<pair<int,int>> sita;

  EulerTour(vector<vector<int>>& G, int root=0){
    int n=G.size();
    order.resize(n);
    sita.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);
      }
      sita[v]=make_pair(order[v],cur-1);
    };
    dfs(root, -1);
  }
};

#line 2 "tree/euler_tour.hpp"

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


/// オイラーツアー
struct EulerTour{
  vector<int> order;
  vector<pair<int,int>> sita;

  EulerTour(vector<vector<int>>& G, int root=0){
    int n=G.size();
    order.resize(n);
    sita.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);
      }
      sita[v]=make_pair(order[v],cur-1);
    };
    dfs(root, -1);
  }
};

Back to top page