unicyclic graph / 1-tree
(include/emthrm/graph/unicyclic_graph.hpp)
閉路をただ一つだけ含む単純連結無向グラフである。俗にある漫画家の名前を用いて表現される 。
時間計算量
$O(\lvert V \rvert)$
仕様
template < typename CostType >
struct UnicyclicGraph ;
メンバ変数
名前
説明
std::vector<bool> is_in_loop
is_in_loop[i]
は頂点 $i$ が閉路に含まれるかを表す。
std::vector<int> belong
belong[i]
は頂点 $i$ を含む木の番号。ただし存在しないときは $-1$ となる。
std::vector<int> mapping
mapping[i]
は頂点 $i$ に対応する木の頂点番号。ただし存在しないときは $-1$ となる。
std::vector<Edge<CostType>> loop
閉路
std::vector<std::vector<int>> invs
invs[i][j]
は木 $i$ の頂点 $j$ に対応する元のグラフの頂点番号を表す。
std::vector<std::vector<std::vector<Edge<CostType>>>> forest
閉路を除いた森
メンバ関数
名前
効果・戻り値
explicit UnicyclicGraph(const int n);
頂点数 $N$ のオブジェクトを構築する。
void add_edge(const int src, const int dst, const CostType cost = 0);
コスト $\mathrm{cost}$ の辺 $(\mathrm{src}, \mathrm{dst})$ を加える。
void build();
構築する。
参考文献
“Harold N. Gabow and Robert E. Tarjan: A linear-time algorithm for finding a minimum spanning pseudoforest, Information Processing Letters , Vol. 27, No. 5, pp. 259–263 (1988). https://doi.org/10.1016/0020-0190(88)90089-0” の Introduction
https://en.wikipedia.org/wiki/Pseudoforest
Submissons
https://yukicoder.me/submissions/649654
Depends on
Verified with
Code
#ifndef EMTHRM_GRAPH_UNICYCLIC_GRAPH_HPP_
#define EMTHRM_GRAPH_UNICYCLIC_GRAPH_HPP_
#include <cassert>
#include <iterator>
#include <queue>
#include <vector>
#include "emthrm/graph/edge.hpp"
namespace emthrm {
template < typename CostType >
struct UnicyclicGraph {
std :: vector < bool > is_in_loop ;
std :: vector < int > belong , mapping ;
std :: vector < Edge < CostType >> loop ;
std :: vector < std :: vector < int >> invs ;
std :: vector < std :: vector < std :: vector < Edge < CostType >>>> forest ;
explicit UnicyclicGraph ( const int n )
: is_in_loop ( n , false ), belong ( n , - 1 ), mapping ( n , - 1 ), n ( n ), graph ( n ) {}
void add_edge ( const int src , const int dst , const CostType cost = 0 ) {
const int id = srcs . size ();
srcs . emplace_back ( src );
dsts . emplace_back ( dst );
costs . emplace_back ( cost );
graph [ src ]. emplace_back ( id );
if ( dst != src ) [[ likely ]] graph [ dst ]. emplace_back ( id );
}
void build () {
dfs ( - 1 , 0 );
std :: queue < int > que ;
for ( const Edge < CostType >& e : loop ) {
const int root = e . src , forest_id = forest . size ();
belong [ root ] = forest_id ;
mapping [ root ] = 0 ;
std :: vector < int > inv { root };
std :: vector < std :: vector < Edge < CostType >>> tree ( 1 );
que . emplace ( root );
while ( ! que . empty ()) {
const int ver = que . front ();
que . pop ();
for ( const int id : graph [ ver ]) {
const int dst = destination ( id , ver );
if ( belong [ dst ] == - 1 && ! is_in_loop [ dst ]) {
const int idx = tree . size ();
belong [ dst ] = forest_id ;
mapping [ dst ] = idx ;
inv . emplace_back ( dst );
tree [ mapping [ ver ]]. emplace_back ( mapping [ ver ], idx , costs [ id ]);
tree . emplace_back ( std :: vector < Edge < CostType >> {
Edge < CostType > ( idx , mapping [ ver ], costs [ id ])});
que . emplace ( dst );
}
}
}
if ( inv . size () == 1 ) {
belong [ root ] = mapping [ root ] = - 1 ;
} else {
invs . emplace_back ( inv );
forest . emplace_back ( tree );
}
}
}
private:
const int n ;
std :: vector < int > srcs , dsts ;
std :: vector < CostType > costs ;
std :: vector < std :: vector < int >> graph ;
int destination ( const int id , const int s ) const {
return ( srcs [ id ] == s ? dsts : srcs )[ id ];
}
bool dfs ( const int prev_id , const int ver ) {
is_in_loop [ ver ] = true ;
for ( const int id : graph [ ver ]) {
if ( id == prev_id ) continue ;
const int dst = destination ( id , ver );
loop . emplace_back ( ver , dst , costs [ id ]);
if ( is_in_loop [ dst ]) {
for ( int i = loop . size () - 1 ; i >= 0 ; -- i ) {
if ( loop [ i ]. src == dst ) {
for ( int j = 0 ; j < i ; ++ j ) {
is_in_loop [ loop [ j ]. src ] = false ;
}
loop . erase ( loop . begin (), std :: next ( loop . begin (), i ));
return true ;
}
}
assert ( false );
}
if ( dfs ( id , dst )) return true ;
loop . pop_back ();
}
is_in_loop [ ver ] = false ;
return false ;
}
};
} // namespace emthrm
#endif // EMTHRM_GRAPH_UNICYCLIC_GRAPH_HPP_
#line 1 "include/emthrm/graph/unicyclic_graph.hpp"
#include <cassert>
#include <iterator>
#include <queue>
#include <vector>
#line 1 "include/emthrm/graph/edge.hpp"
/**
* @title 辺
*/
#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_
#include <compare>
namespace emthrm {
template < typename CostType >
struct Edge {
CostType cost ;
int src , dst ;
explicit Edge ( const int src , const int dst , const CostType cost = 0 )
: cost ( cost ), src ( src ), dst ( dst ) {}
auto operator <=> ( const Edge & x ) const = default ;
};
} // namespace emthrm
#endif // EMTHRM_GRAPH_EDGE_HPP_
#line 10 "include/emthrm/graph/unicyclic_graph.hpp"
namespace emthrm {
template < typename CostType >
struct UnicyclicGraph {
std :: vector < bool > is_in_loop ;
std :: vector < int > belong , mapping ;
std :: vector < Edge < CostType >> loop ;
std :: vector < std :: vector < int >> invs ;
std :: vector < std :: vector < std :: vector < Edge < CostType >>>> forest ;
explicit UnicyclicGraph ( const int n )
: is_in_loop ( n , false ), belong ( n , - 1 ), mapping ( n , - 1 ), n ( n ), graph ( n ) {}
void add_edge ( const int src , const int dst , const CostType cost = 0 ) {
const int id = srcs . size ();
srcs . emplace_back ( src );
dsts . emplace_back ( dst );
costs . emplace_back ( cost );
graph [ src ]. emplace_back ( id );
if ( dst != src ) [[ likely ]] graph [ dst ]. emplace_back ( id );
}
void build () {
dfs ( - 1 , 0 );
std :: queue < int > que ;
for ( const Edge < CostType >& e : loop ) {
const int root = e . src , forest_id = forest . size ();
belong [ root ] = forest_id ;
mapping [ root ] = 0 ;
std :: vector < int > inv { root };
std :: vector < std :: vector < Edge < CostType >>> tree ( 1 );
que . emplace ( root );
while ( ! que . empty ()) {
const int ver = que . front ();
que . pop ();
for ( const int id : graph [ ver ]) {
const int dst = destination ( id , ver );
if ( belong [ dst ] == - 1 && ! is_in_loop [ dst ]) {
const int idx = tree . size ();
belong [ dst ] = forest_id ;
mapping [ dst ] = idx ;
inv . emplace_back ( dst );
tree [ mapping [ ver ]]. emplace_back ( mapping [ ver ], idx , costs [ id ]);
tree . emplace_back ( std :: vector < Edge < CostType >> {
Edge < CostType > ( idx , mapping [ ver ], costs [ id ])});
que . emplace ( dst );
}
}
}
if ( inv . size () == 1 ) {
belong [ root ] = mapping [ root ] = - 1 ;
} else {
invs . emplace_back ( inv );
forest . emplace_back ( tree );
}
}
}
private:
const int n ;
std :: vector < int > srcs , dsts ;
std :: vector < CostType > costs ;
std :: vector < std :: vector < int >> graph ;
int destination ( const int id , const int s ) const {
return ( srcs [ id ] == s ? dsts : srcs )[ id ];
}
bool dfs ( const int prev_id , const int ver ) {
is_in_loop [ ver ] = true ;
for ( const int id : graph [ ver ]) {
if ( id == prev_id ) continue ;
const int dst = destination ( id , ver );
loop . emplace_back ( ver , dst , costs [ id ]);
if ( is_in_loop [ dst ]) {
for ( int i = loop . size () - 1 ; i >= 0 ; -- i ) {
if ( loop [ i ]. src == dst ) {
for ( int j = 0 ; j < i ; ++ j ) {
is_in_loop [ loop [ j ]. src ] = false ;
}
loop . erase ( loop . begin (), std :: next ( loop . begin (), i ));
return true ;
}
}
assert ( false );
}
if ( dfs ( id , dst )) return true ;
loop . pop_back ();
}
is_in_loop [ ver ] = false ;
return false ;
}
};
} // namespace emthrm
Back to top page