#line 1 "tests/graph/eulerian-walk/libchecker-undirected.test.cpp"
#include <bits/stdc++.h>
using namespace std ;
#define rep(i, n) for (int i = 0; i < (n); ++i)
using ll = long long ;
using ull = unsigned long long ;
#line 2 "library/graph/eulerian-walk.hpp"
#include <concepts>
#include <optional>
#line 8 "library/graph/eulerian-walk.hpp"
using namespace std ;
#line 2 "library/_internal/graph/eulerian-walk.hpp"
#line 8 "library/_internal/graph/eulerian-walk.hpp"
using namespace std ;
#line 2 "library/data-structure/graph.hpp"
#line 6 "library/data-structure/graph.hpp"
using namespace std ;
#line 2 "library/_internal/graph-base.hpp"
#line 4 "library/_internal/graph-base.hpp"
#include <type_traits>
using namespace std ;
namespace asalib {
namespace _internal {
class graph_base {};
class notweighted_graph_base : public graph_base {};
class weighted_graph_base : public graph_base {};
template < typename T >
concept is_graph = is_base_of_v < graph_base , T > ;
template < typename T >
concept notweighted_graph = is_base_of_v < notweighted_graph_base , T > ;
template < typename T >
concept weighted_graph = is_base_of_v < weighted_graph_base , T > ;
using adjlist_t = vector < vector < pair < size_t , size_t >>> ;
using edgelist_t = vector < pair < size_t , size_t >> ;
} // namespace _internal
} // namespace asalib
#line 9 "library/data-structure/graph.hpp"
namespace asalib {
namespace graph {
class graph : public _internal :: notweighted_graph_base {
public:
graph () : n_vertex ( 0 ), n_edge ( 0 ) {}
explicit graph ( size_t n_vertex ) : n_vertex ( n_vertex ), n_edge ( 0 ) {
adj_list . reserve ( n_vertex );
adj_list . resize ( n_vertex );
}
void add_edge ( size_t v1 , size_t v2 ) {
assert ( 0 <= v1 && v1 < n_vertex );
assert ( 0 <= v2 && v2 < n_vertex );
adj_list [ v1 ]. push_back ({ v2 , n_edge });
adj_list [ v2 ]. push_back ({ v1 , n_edge });
edge_list . push_back ({ v1 , v2 });
++ n_edge ;
}
// (v1, v2)
pair < size_t , size_t > get_edge ( size_t edgeId ) const {
assert ( 0 <= edgeId && edgeId < n_edge );
return edge_list [ edgeId ];
}
// (v2, edgeId)
vector < pair < size_t , size_t >> get_adj ( size_t vertex ) const {
assert ( 0 <= vertex && vertex < n_vertex );
return adj_list [ vertex ];
}
// ---------- prototype ---------- //
optional < pair < vector < size_t > , vector < size_t >>> cycle () const ;
bool is_connected () const ;
optional < pair < vector < size_t > , vector < size_t >>> eulerian_walk () const ;
private:
size_t n_vertex , n_edge ;
asalib :: _internal :: adjlist_t adj_list ;
asalib :: _internal :: edgelist_t edge_list ;
};
} // namespace graph
} // namespace asalib
#line 11 "library/_internal/graph/eulerian-walk.hpp"
namespace asalib {
namespace _internal {
namespace graph {
template < bool is_directed >
pair < vector < size_t > , vector < size_t >> eulerian_walk ( const size_t & n , const edgelist_t & Edges , const size_t & start_v , const size_t & end_v ) {
// グラフを変換するパート
vector < queue < size_t >> Graph ( n );
for ( size_t i = 0 ; i < Edges . size (); ++ i ) {
const auto & [ u , v ] = Edges [ i ];
Graph [ u ]. push ( i );
if constexpr ( ! is_directed ) Graph [ v ]. push ( i );
}
vector < bool > used ( Edges . size (), false );
// 適当にパスを見つけるやつ (これはオイラー路が存在することが確定してるからできる技)
auto find_path = [ & ]( size_t from , size_t to , vector < size_t >& vs , vector < size_t >& eds ) {
size_t now = from ;
if ( Graph [ now ]. empty ()) return false ;
do {
assert ( ! Graph [ now ]. empty ());
size_t e_idx = Graph [ now ]. front ();
Graph [ now ]. pop ();
if ( used [ e_idx ]) continue ;
used [ e_idx ] = true ;
eds . push_back ( e_idx );
vs . push_back ( now );
const auto & [ u , v ] = Edges [ e_idx ];
if ( u == now ) {
now = v ;
}
else {
assert ( now == v );
now = u ;
}
} while ( now != to );
vs . push_back ( to );
return true ;
};
// 適当に start_v -> end_v のパスを作るパート
vector < size_t > vs = {}, eds = {};
find_path ( start_v , end_v , vs , eds );
assert ( vs . size () == eds . size () + 1 );
constexpr size_t ign = - 1 ;
eds . push_back ( ign );
// 別の道があれば寄り道して辺を全部使うパート (閉路になるはず)
vector < size_t > res_vs , res_eds ;
for ( size_t i = 0 ; i < eds . size (); ++ i ) {
stack < size_t > v , e ;
v . push ( vs [ i ]), e . push ( eds [ i ]);
while ( ! v . empty ()) {
assert ( v . size () == e . size ());
size_t now = v . top ();
size_t e_idx = e . top ();
vector < size_t > tmpvs , tmpeds ;
if ( find_path ( now , now , tmpvs , tmpeds )) {
assert ( tmpvs . front () == now && tmpvs . back () == now );
assert ( tmpvs . size () == tmpeds . size () + 1 );
tmpvs . pop_back ();
reverse ( tmpvs . begin (), tmpvs . end ());
reverse ( tmpeds . begin (), tmpeds . end ());
for ( const auto & ver : tmpvs ) v . push ( ver );
for ( const auto & edg : tmpeds ) e . push ( edg );
}
else {
v . pop (), e . pop ();
res_vs . push_back ( now );
res_eds . push_back ( e_idx );
}
}
}
assert ( res_eds . back () == ign );
res_eds . pop_back ();
assert ( res_vs . size () == res_eds . size () + 1 );
assert ( res_eds . size () == Edges . size ());
return make_pair ( res_vs , res_eds );
}
} // namespace graph
} // namespace _internal
} // namespace asalib
#line 2 "library/data-structure/digraph.hpp"
#line 6 "library/data-structure/digraph.hpp"
using namespace std ;
#line 10 "library/data-structure/digraph.hpp"
namespace asalib {
namespace graph {
class digraph : public _internal :: notweighted_graph_base {
public:
digraph () : n_vertex ( 0 ), n_edge ( 0 ) {}
explicit digraph ( size_t n_vertex ) : n_vertex ( n_vertex ), n_edge ( 0 ) {
adj_list . reserve ( n_vertex );
adj_list . resize ( n_vertex );
adj_list_rev . reserve ( n_vertex );
adj_list_rev . resize ( n_vertex );
underlying_graph = graph ( n_vertex );
}
void add_edge ( size_t from , size_t to ) {
assert ( 0 <= from && from < n_vertex );
assert ( 0 <= to && to < n_vertex );
adj_list [ from ]. push_back ({ to , n_edge });
adj_list_rev [ to ]. push_back ({ from , n_edge });
edge_list . push_back ({ from , to });
underlying_graph . add_edge ( from , to );
++ n_edge ;
}
// (from, to)
pair < size_t , size_t > get_edge ( size_t edgeId ) const {
assert ( 0 <= edgeId && edgeId < n_edge );
return edge_list [ edgeId ];
}
// (to, edgeId)
vector < pair < size_t , size_t >> get_adj ( size_t vertex ) const {
assert ( 0 <= vertex && vertex < n_vertex );
return adj_list [ vertex ];
}
// (from, edgeId)
vector < pair < size_t , size_t >> get_adjrev ( size_t vertex ) const {
assert ( 0 <= vertex && vertex < n_vertex );
return adj_list_rev [ vertex ];
}
// ---------- prototype ---------- //
vector < vector < size_t >> scc () const ;
optional < pair < vector < size_t > , vector < size_t >>> cycle () const ;
bool is_connected () const ;
optional < pair < vector < size_t > , vector < size_t >>> eulerian_walk () const ;
private:
size_t n_vertex , n_edge ;
asalib :: _internal :: adjlist_t adj_list , adj_list_rev ;
asalib :: _internal :: edgelist_t edge_list ;
graph underlying_graph ;
};
} // namespace graph
} // namespace asalib
#line 2 "library/graph/connection.hpp"
using namespace std ;
#line 2 "library/_internal/graph/connection.hpp"
#line 5 "library/_internal/graph/connection.hpp"
using namespace std ;
#line 8 "library/_internal/graph/connection.hpp"
namespace asalib {
namespace _internal {
namespace graph {
bool is_connected ( const adjlist_t & adjlist ) {
vector < bool > visited ( adjlist . size (), false );
function < void ( size_t ) > dfs = [ & ]( size_t v ) {
visited [ v ] = true ;
for ( const auto & [ u , _ ] : adjlist [ v ])
if ( ! visited [ u ]) dfs ( u );
};
dfs ( 0 );
return all_of ( visited . begin (), visited . end (), []( bool v ) {
return v ;
});
}
} // namespace graph
} // namespace _internal
} // namespace asalib
#line 8 "library/graph/connection.hpp"
namespace asalib {
namespace graph {
bool digraph :: is_connected () const { return _internal :: graph :: is_connected ( adj_list ); }
bool graph :: is_connected () const { return _internal :: graph :: is_connected ( adj_list ); }
} // namespace graph
} // namespace asalib
#line 14 "library/graph/eulerian-walk.hpp"
namespace asalib {
namespace graph {
optional < pair < vector < size_t > , vector < size_t >>> digraph :: eulerian_walk () const {
constexpr size_t None = - 1 ;
// もし辺がなければオイラーグラフ、任意の頂点を返す
if ( edge_list . empty ()) [[ unlikely ]]
return make_pair ( vector < size_t > { 0 }, vector < size_t > {});
// 辺がない頂点を除外したグラフを作る
size_t n_vertex_withedge = 0 ;
vector < size_t > id ( n_vertex , None );
for ( const auto & [ u , v ] : edge_list ) {
if ( id [ u ] == None ) id [ u ] = n_vertex_withedge ++ ;
if ( id [ v ] == None ) id [ v ] = n_vertex_withedge ++ ;
}
vector < size_t > idrev ( n_vertex_withedge , None );
for ( size_t i = 0 ; i < n_vertex ; ++ i )
if ( id [ i ] != None ) idrev [ id [ i ]] = i ;
asalib :: graph :: digraph newGraph ( n_vertex_withedge );
for ( const auto & [ u , v ] : edge_list ) newGraph . add_edge ( id [ u ], id [ v ]);
// 有向グラフの場合、基底無向グラフが連結でなければ存在しない
if ( ! newGraph . underlying_graph . is_connected ()) return nullopt ;
// オイラーグラフとなるか判定
vector < size_t > in ( n_vertex_withedge , 0 ), out ( n_vertex_withedge , 0 );
for ( const auto & [ u , v ] : edge_list ) ++ out [ id [ u ]], ++ in [ id [ v ]];
size_t start = None , end = None ;
for ( size_t i = 0 ; i < n_vertex_withedge ; ++ i ) {
if ( in [ i ] == out [ i ]) continue ;
if ( in [ i ] + 1 == out [ i ]) {
if ( start != None ) return nullopt ;
start = i ;
continue ;
}
if ( in [ i ] == out [ i ] + 1 ) {
if ( end != None ) return nullopt ;
end = i ;
continue ;
}
return nullopt ;
}
if (( start == None ) xor ( end == None )) return nullopt ;
if ( start == None ) {
assert ( end == None );
start = end = 0 ;
}
auto [ vertexes , edges ] = asalib :: _internal :: graph :: eulerian_walk < true > ( n_vertex_withedge , newGraph . edge_list , start , end );
vector < size_t > vertexes_original ;
for ( const auto & v : vertexes ) vertexes_original . push_back ( idrev [ v ]);
return make_pair ( vertexes_original , edges );
}
optional < pair < vector < size_t > , vector < size_t >>> graph :: eulerian_walk () const {
constexpr size_t None = - 1 ;
// もし辺がなければオイラーグラフ、任意の頂点を返す
if ( edge_list . empty ()) [[ unlikely ]]
return make_pair ( vector < size_t > { 0 }, vector < size_t > {});
// 辺のない頂点を除外したグラフを作る
size_t n_vertex_withedge = 0 ;
vector < size_t > id ( n_vertex , None );
for ( const auto & [ u , v ] : edge_list ) {
if ( id [ u ] == None ) id [ u ] = n_vertex_withedge ++ ;
if ( id [ v ] == None ) id [ v ] = n_vertex_withedge ++ ;
}
vector < size_t > idrev ( n_vertex_withedge , None );
for ( size_t i = 0 ; i < n_vertex ; ++ i )
if ( id [ i ] != None ) idrev [ id [ i ]] = i ;
asalib :: graph :: graph newGraph ( n_vertex_withedge );
for ( const auto & [ u , v ] : edge_list ) newGraph . add_edge ( id [ u ], id [ v ]);
// 連結でなければ存在しない
if ( ! newGraph . is_connected ()) return nullopt ;
vector < size_t > deg ( n_vertex_withedge , 0 );
for ( const auto & [ u , v ] : edge_list ) ++ deg [ id [ u ]], ++ deg [ id [ v ]];
size_t start = None , end = None ;
for ( size_t i = 0 ; i < n_vertex_withedge ; ++ i ) {
if ( deg [ i ] % 2 == 0 ) continue ;
if ( start == None )
start = i ;
else if ( end == None )
end = i ;
else
return nullopt ;
}
if ( start != None && end == None ) return nullopt ;
if ( start == None ) {
assert ( end == None );
start = end = 0 ;
}
auto [ vertexes , edges ] = asalib :: _internal :: graph :: eulerian_walk < false > ( n_vertex_withedge , newGraph . edge_list , start , end );
vector < size_t > vertexes_original ;
for ( const auto & v : vertexes ) vertexes_original . push_back ( idrev [ v ]);
return make_pair ( vertexes_original , edges );
}
} // namespace graph
} // namespace asalib
#line 9 "tests/graph/eulerian-walk/libchecker-undirected.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/eulerian_trail_undirected"
void solve () {
int n , m ;
cin >> n >> m ;
asalib :: graph :: graph Graph ( n );
rep ( _ , m ) {
int u , v ;
cin >> u >> v ;
Graph . add_edge ( u , v );
}
auto res = Graph . eulerian_walk ();
if ( ! res . has_value ()) {
cout << "No" << endl ;
}
else {
cout << "Yes" << endl ;
auto [ vs , es ] = res . value ();
rep ( i , vs . size ()) {
if ( i ) cout << " " ;
cout << vs [ i ];
}
cout << endl ;
rep ( i , es . size ()) {
if ( i ) cout << " " ;
cout << es [ i ];
}
cout << endl ;
}
}
int main () {
cin . tie ( nullptr ) -> sync_with_stdio ( false );
int t ;
cin >> t ;
while ( t -- ) solve ();
return 0 ;
}
Copy Bundle