Euler tour (Vertex)
(Mylib/Graph/TreeUtils/euler_tour_vertex.cpp)
Operations
Requirements
Notes
Problems
References
Depends on
Verified with
Code
#pragma once
#include <vector>
#include "Mylib/Graph/Template/graph.cpp"
namespace haar_lib {
template < typename T >
class euler_tour_vertex {
int pos_ = 0 ;
std :: vector < int > begin_ , end_ ;
void dfs ( int cur , int par , const tree < T > & tr ) {
begin_ [ cur ] = pos_ ++ ;
for ( auto & e : tr [ cur ]) {
if ( e . to == par ) continue ;
dfs ( e . to , cur , tr );
}
end_ [ cur ] = pos_ ;
}
public:
euler_tour_vertex () {}
euler_tour_vertex ( const tree < T > & tr , int root ) : begin_ ( tr . size ()), end_ ( tr . size ()) {
dfs ( root , - 1 , tr );
}
template < typename F > // F = std::function<void(int, int)>
void subtree_query ( int i , const F & f ) {
f ( begin_ [ i ], end_ [ i ]);
}
template < typename F > // F = std::function<void(int)>
void point_query ( int i , const F & f ) {
f ( begin_ [ i ]);
}
};
} // namespace haar_lib
#line 2 "Mylib/Graph/TreeUtils/euler_tour_vertex.cpp"
#include <vector>
#line 2 "Mylib/Graph/Template/graph.cpp"
#include <iostream>
#line 4 "Mylib/Graph/Template/graph.cpp"
namespace haar_lib {
template < typename T >
struct edge {
int from , to ;
T cost ;
int index = - 1 ;
edge () {}
edge ( int from , int to , T cost ) : from ( from ), to ( to ), cost ( cost ) {}
edge ( int from , int to , T cost , int index ) : from ( from ), to ( to ), cost ( cost ), index ( index ) {}
};
template < typename T >
struct graph {
using weight_type = T ;
using edge_type = edge < T > ;
std :: vector < std :: vector < edge < T >>> data ;
auto & operator []( size_t i ) { return data [ i ]; }
const auto & operator []( size_t i ) const { return data [ i ]; }
auto begin () const { return data . begin (); }
auto end () const { return data . end (); }
graph () {}
graph ( int N ) : data ( N ) {}
bool empty () const { return data . empty (); }
int size () const { return data . size (); }
void add_edge ( int i , int j , T w , int index = - 1 ) {
data [ i ]. emplace_back ( i , j , w , index );
}
void add_undirected ( int i , int j , T w , int index = - 1 ) {
add_edge ( i , j , w , index );
add_edge ( j , i , w , index );
}
template < size_t I , bool DIRECTED = true , bool WEIGHTED = true >
void read ( int M ) {
for ( int i = 0 ; i < M ; ++ i ) {
int u , v ;
std :: cin >> u >> v ;
u -= I ;
v -= I ;
T w = 1 ;
if ( WEIGHTED ) std :: cin >> w ;
if ( DIRECTED )
add_edge ( u , v , w , i );
else
add_undirected ( u , v , w , i );
}
}
};
template < typename T >
using tree = graph < T > ;
} // namespace haar_lib
#line 4 "Mylib/Graph/TreeUtils/euler_tour_vertex.cpp"
namespace haar_lib {
template < typename T >
class euler_tour_vertex {
int pos_ = 0 ;
std :: vector < int > begin_ , end_ ;
void dfs ( int cur , int par , const tree < T > & tr ) {
begin_ [ cur ] = pos_ ++ ;
for ( auto & e : tr [ cur ]) {
if ( e . to == par ) continue ;
dfs ( e . to , cur , tr );
}
end_ [ cur ] = pos_ ;
}
public:
euler_tour_vertex () {}
euler_tour_vertex ( const tree < T > & tr , int root ) : begin_ ( tr . size ()), end_ ( tr . size ()) {
dfs ( root , - 1 , tr );
}
template < typename F > // F = std::function<void(int, int)>
void subtree_query ( int i , const F & f ) {
f ( begin_ [ i ], end_ [ i ]);
}
template < typename F > // F = std::function<void(int)>
void point_query ( int i , const F & f ) {
f ( begin_ [ i ]);
}
};
} // namespace haar_lib
Back to top page