competitive/graph/
topological_sort.rs

1use super::SparseGraph;
2
3impl<D> SparseGraph<D> {
4    pub fn topological_sort(&self) -> Vec<usize> {
5        let mut indeg = vec![0; self.vertices_size()];
6        let mut res = vec![];
7        for a in self.vertices().flat_map(|u| self.adjacencies(u)) {
8            indeg[a.to] += 1;
9        }
10        let mut stack = self
11            .vertices()
12            .filter(|&u| indeg[u] == 0)
13            .collect::<Vec<_>>();
14        while let Some(u) = stack.pop() {
15            res.push(u);
16            for a in self.adjacencies(u) {
17                indeg[a.to] -= 1;
18                if indeg[a.to] == 0 {
19                    stack.push(a.to);
20                }
21            }
22        }
23        res
24    }
25}