haar_lib/graph/
tsort.rs

1//! トポロジカルソート
2
3use crate::graph::*;
4use std::collections::VecDeque;
5
6/// トポロジカルソート
7///
8/// **Time complexity** $O(V)$
9///
10/// gがDAGのとき、トポロジカルソートした結果をSomeに包んで返す。
11/// そうでなければ、Noneを返す。
12pub fn tsort<E: EdgeTrait>(g: &Graph<Directed, E>) -> Option<Vec<usize>> {
13    let n = g.len();
14    let mut indeg = vec![0; n];
15
16    for e in g.nodes_iter().flat_map(|v| &v.edges) {
17        indeg[e.to()] += 1;
18    }
19
20    let mut q: VecDeque<_> = indeg
21        .iter()
22        .enumerate()
23        .filter_map(|(i, &x)| (x == 0).then_some(i))
24        .collect();
25
26    let mut ret = vec![];
27
28    while let Some(cur) = q.pop_front() {
29        ret.push(cur);
30        for e in g.nodes[cur].edges.iter() {
31            let to = e.to();
32            indeg[to] -= 1;
33            if indeg[to] == 0 {
34                q.push_back(to);
35            }
36        }
37    }
38
39    (ret.len() == n).then_some(ret)
40}
haar_lib/graph/tsort.rs

haar_lib/graph/
tsort.rs
