Function nekolib::graph::scc

source · 
pub fn scc<V, E>(
    n: usize,
    vs: impl Iterator<Item = V>,
    index: impl Fn(&V) -> usize + Copy,
    delta: impl Fn(&V) -> E + Copy
) -> Vec<usize>where
    E: Iterator<Item = V>,
Expand description

lowlink に基づく強連結成分分解。

Parameters

  • n: 頂点数
  • vs: 頂点集合
  • index: 頂点から添字への番号づけをする関数
  • delta: 頂点 v と関数 search を受け取る関数

delta は、v の各隣接頂点 nv に対して、search(nv) を呼び出す必要がある。

Return value

index(v) 番目の要素が v の属する強連結成分の番号である配列。 番号づけはトポロジカル順に行われる。

Examples

(0) ---> (1) ---> (3) ---> (5) ---> (6) ---> (7)
 ^        |        |        ^        ^        |
 |        v        v        |        |        |
(4) <--- (2)      (9)       +------ (8) <-----+

use nekolib::graph::scc;

let g = vec![
    vec![1],
    vec![2, 3],
    vec![4],
    vec![5, 9],
    vec![0],
    vec![6],
    vec![7],
    vec![8],
    vec![5, 6],
    vec![],
];
let index = |&v: &usize| v;
let delta = |&v: &usize| g[v].iter().cloned();
let comp_id = scc(10, 0..10, index, delta);

assert_eq!(comp_id, vec![0, 0, 0, 1, 0, 3, 3, 3, 3, 2]);

Complexity

$O(|V|+|E|)$ 時間。

References