topological_sort/
lib.rs

1/// 有向グラフの頂点をトポロジカル順に並べて返します。グラフが DAG でなければ None を返します。
2///
3/// # Examples
4/// ```
5/// use topological_sort::topological_sort;
6///
7/// let order = topological_sort(4, &[(0, 1), (0, 2), (1, 3), (2, 3)]);
8/// assert!(order == Some(vec![0, 1, 2, 3]) || order == Some(vec![0, 2, 1, 3]));
9/// ```
10pub fn topological_sort(n: usize, edges: &[(usize, usize)]) -> Option<Vec<usize>> {
11    use std::collections::VecDeque;
12
13    let mut g = vec![vec![]; n];
14    let mut in_deg = vec![0; n];
15    for &(s, t) in edges {
16        g[s].push(t);
17        in_deg[t] += 1;
18    }
19
20    let mut order = Vec::new();
21    let mut que = VecDeque::new();
22    #[allow(clippy::needless_range_loop)]
23    for s in 0..n {
24        if in_deg[s] == 0 {
25            order.push(s);
26            que.push_back(s);
27        }
28    }
29    while let Some(u) = que.pop_front() {
30        for &v in &g[u] {
31            in_deg[v] -= 1;
32            if in_deg[v] == 0 {
33                order.push(v);
34                que.push_back(v);
35            }
36        }
37    }
38    assert!(order.len() <= n);
39    if order.len() == n {
40        Some(order)
41    } else {
42        None
43    }
44}
45
46#[cfg(test)]
47mod tests {
48    use crate::topological_sort;
49
50    #[test]
51    fn two_ways() {
52        let order = topological_sort(4, &[(0, 1), (0, 2), (1, 3), (2, 3)]);
53        assert!(order == Some(vec![0, 1, 2, 3]) || order == Some(vec![0, 2, 1, 3]));
54    }
55
56    #[test]
57    fn line() {
58        let order = topological_sort(4, &[(0, 1), (1, 2), (2, 3)]);
59        assert_eq!(order, Some(vec![0, 1, 2, 3]));
60    }
61
62    #[test]
63    fn contain_cycle() {
64        let order = topological_sort(5, &[(0, 1), (1, 2), (2, 3), (3, 1), (3, 4)]);
65        assert_eq!(order, None);
66    }
67}
topological_sort/lib.rs

topological_sort/
lib.rs
