Kyopro Library
 
読み取り中…
検索中…
一致する文字列を見つけられません
scc.hpp
[詳解]
1#pragma once
2#include"../../kyopro_library/template.hpp"
3
4/// @brief 強連結成分分解の情報
5struct SccInfo {
6 vector<vector<int>> members; ///< 各強連結成分の頂点
7 vector<vector<int>> graph_decomposed; ///< 強連結成分による分解グラフ
8 vector<int> group; ///< 各頂点の所属する強連結成分の番号
9};
10
11/// @brief グラフ g の強連結成分分解を行う
12/// @brief { 各強連結成分の頂点, 強連結成分による分解グラフ, 各頂点の所属する強連結成分の番号 } を返す
13/// @note O(V+E)
14SccInfo SccDecomposition(const vector<vector<int>>& g) {
15 int n=g.size();
16 vector<vector<int>> g2(n);
17 for(int i=0; i<n; i++) for(int j: g[i]) g2[j].push_back(i);
18 vector<int> order,component(n,-1),seen(n,false);
19
20 auto dfs=[&](auto dfs, int now)-> void {
21 seen[now]=true;
22 for(int nxt: g[now]) if(!seen[nxt]) dfs(dfs,nxt);
23 order.push_back(now);
24 };
25
26 auto dfs2=[&](auto dfs2, int now, int idx)-> void {
27 component[now]=idx;
28 for(int nxt: g2[now]) if(component[nxt]==-1) dfs2(dfs2,nxt,idx);
29 };
30
31 for(int i=0; i<n; i++) if(!seen[i]) dfs(dfs,i);
32
33 reverse(order.begin(),order.end());
34 int idx=0;
35 for(int now:order) if(component[now]==-1) dfs2(dfs2,now,idx),idx++;
36
37 int n_n=*max_element(component.begin(),component.end())+1;
38 vector<vector<int>> ret(n_n),ret2(n_n);
39 for(int i=0; i<n; i++) ret[component[i]].push_back(i);
40 for(int i=0; i<n; i++) for(int j: g[i]) if(component[i]!=component[j]) ret2[component[i]].push_back(component[j]);
41 for(int i=0; i<n_n; i++) UQ(ret2[i]);
42
43 return {ret,ret2,component};
44}
SccInfo SccDecomposition(const vector< vector< int > > &g)
グラフ g の強連結成分分解を行う
Definition scc.hpp:14
強連結成分分解の情報
Definition scc.hpp:5
vector< vector< int > > graph_decomposed
強連結成分による分解グラフ
Definition scc.hpp:7
vector< int > group
各頂点の所属する強連結成分の番号
Definition scc.hpp:8
vector< vector< int > > members
各強連結成分の頂点
Definition scc.hpp:6