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 { Some(order) } else { None }
40}
41
42#[cfg(test)]
43mod tests {
44    use crate::topological_sort;
45
46    #[test]
47    fn two_ways() {
48        let order = topological_sort(4, &[(0, 1), (0, 2), (1, 3), (2, 3)]);
49        assert!(order == Some(vec![0, 1, 2, 3]) || order == Some(vec![0, 2, 1, 3]));
50    }
51
52    #[test]
53    fn line() {
54        let order = topological_sort(4, &[(0, 1), (1, 2), (2, 3)]);
55        assert_eq!(order, Some(vec![0, 1, 2, 3]));
56    }
57
58    #[test]
59    fn contain_cycle() {
60        let order = topological_sort(5, &[(0, 1), (1, 2), (2, 3), (3, 1), (3, 4)]);
61        assert_eq!(order, None);
62    }
63}
topological_sort/lib.rs

topological_sort/
lib.rs
