nekolib/graph/
scc_.rs

1//! 強連結成分分解。
2
3/// lowlink に基づく強連結成分分解。
4///
5/// # Parameters
6/// - `n`: 頂点数
7/// - `vs`: 頂点集合
8/// - `index`: 頂点から添字への番号づけをする関数
9/// - `delta`: 頂点 `v` と関数 `search` を受け取る関数
10///
11/// `delta` は、`v` の各隣接頂点 `nv` に対して、`search(nv)`
12/// を呼び出す必要がある。
13///
14/// # Return value
15/// `index(v)` 番目の要素が `v` の属する強連結成分の番号である配列。
16/// 番号づけはトポロジカル順に行われる。
17///
18/// # Examples
19///
20/// ```text
21/// (0) ---> (1) ---> (3) ---> (5) ---> (6) ---> (7)
22///  ^        |        |        ^        ^        |
23///  |        v        v        |        |        |
24/// (4) <--- (2)      (9)       +------ (8) <-----+
25/// ```
26///
27/// ```
28/// use nekolib::graph::scc;
29///
30/// let g = vec![
31///     vec![1],
32///     vec![2, 3],
33///     vec![4],
34///     vec![5, 9],
35///     vec![0],
36///     vec![6],
37///     vec![7],
38///     vec![8],
39///     vec![5, 6],
40///     vec![],
41/// ];
42/// let index = |&v: &usize| v;
43/// let delta = |&v: &usize| g[v].iter().cloned();
44/// let comp_id = scc(10, 0..10, index, delta);
45///
46/// assert_eq!(comp_id, vec![0, 0, 0, 1, 0, 3, 3, 3, 3, 2]);
47/// ```
48///
49/// # Complexity
50/// $O(|V|+|E|)$ 時間。
51///
52/// # References
53/// - <https://niuez.github.io/posts/impl_abstract_dijkstra/>
54pub fn scc<V, E>(
55    n: usize,
56    vs: impl Iterator<Item = V>,
57    index: impl Fn(&V) -> usize + Copy,
58    delta: impl Fn(&V) -> E + Copy,
59) -> Vec<usize>
60where
61    E: Iterator<Item = V>,
62{
63    struct State {
64        scc: Vec<Vec<usize>>,
65        num: Vec<usize>,
66        low: Vec<usize>,
67        s: Vec<usize>,
68        ins: Vec<bool>,
69        t: usize,
70    }
71
72    fn dfs<V, E>(
73        v: V,
74        index: impl Fn(&V) -> usize + Copy,
75        delta: impl Fn(&V) -> E + Copy,
76        state: &mut State,
77    ) where
78        E: Iterator<Item = V>,
79    {
80        state.t += 1;
81        let vi = index(&v);
82        state.low[vi] = state.t;
83        state.num[vi] = state.t;
84        state.s.push(vi);
85        state.ins[vi] = true;
86        for nv in delta(&v) {
87            let nvi = index(&nv);
88            if state.num[nvi] == 0 {
89                dfs(nv, index, delta, state);
90                state.low[vi] = state.low[vi].min(state.low[nvi]);
91            } else if state.ins[nvi] {
92                state.low[vi] = state.low[vi].min(state.num[nvi]);
93            }
94        }
95        if state.low[vi] == state.num[vi] {
96            let mut tmp = vec![];
97            loop {
98                let nvi = state.s.pop().unwrap();
99                state.ins[nvi] = false;
100                tmp.push(nvi);
101                if vi == nvi {
102                    break;
103                }
104            }
105            state.scc.push(tmp);
106        }
107    }
108
109    let mut state = State {
110        scc: vec![],
111        num: vec![0; n],
112        low: vec![0; n],
113        s: vec![],
114        ins: vec![false; n],
115        t: 0,
116    };
117
118    for v in vs {
119        if state.num[index(&v)] == 0 {
120            dfs(v, index, delta, &mut state);
121        }
122    }
123
124    let mut res = vec![0; n];
125    for i in 0..state.scc.len() {
126        for &c in &state.scc[i] {
127            res[c] = state.scc.len() - i - 1;
128        }
129    }
130
131    res
132}
nekolib/graph/scc_.rs

nekolib/graph/
scc_.rs
