1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140

//! An implementation of Tarjan's Strongly Connected Components algorithm using an adjacency list.
//!
//! - Time complexity: $O(V+E)$
//!
//! # Resources
//!
//! - [W. Fiset's video](https://www.youtube.com/watch?v=wUgWX0nc4NY&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=23)

use crate::algo::graph::UnweightedAdjacencyList;
use std::cmp::min;

const UNVISITED: i32 = -1;
struct SccSolver<'a> {
    g: &'a UnweightedAdjacencyList,
    ids: Vec<i32>,
    stack: Vec<usize>,
    on_stack: Vec<bool>,
    id: i32,
    low_link: Vec<i32>,
    sccs: Vec<Vec<usize>>,
}

impl<'a> SccSolver<'a> {
    fn new(g: &'a UnweightedAdjacencyList) -> Self {
        let n = g.vertices_count();
        Self {
            g,
            ids: vec![UNVISITED; n],
            sccs: Vec::new(),
            low_link: vec![0; n],
            id: 0,
            stack: Vec::new(),
            on_stack: vec![false; n],
        }
    }
}

impl UnweightedAdjacencyList {
    pub fn scc(&self) -> SccResult {
        let n = self.vertices_count();
        let mut s = SccSolver::new(self);

        fn _dfs(s: &mut SccSolver, at: usize) {
            s.low_link[at] = s.id;
            s.ids[at] = s.id;
            s.id += 1;
            s.stack.push(at);
            s.on_stack[at] = true;
            // visit all neighbours and min low-link on callback
            for &neighbour in &s.g[at] {
                if s.ids[neighbour] == UNVISITED {
                    _dfs(s, neighbour);
                }
                if s.on_stack[neighbour] {
                    s.low_link[at] = min(s.low_link[at], s.low_link[neighbour])
                }
            }
            // after having visited all the neighbours of `at` if we're at the start of
            // a SCC empty the seen stack until we're back to the start of the SCC
            if s.ids[at] == s.low_link[at] {
                let mut this_scc = Vec::new();
                while let Some(node) = s.stack.pop() {
                    s.on_stack[node] = false;
                    s.low_link[node] = s.ids[at];
                    this_scc.push(node);
                    if node == at {
                        s.sccs.push(this_scc);
                        break;
                    }
                }
            }
        }
        for i in 0..n {
            if s.ids[i] == UNVISITED {
                _dfs(&mut s, i);
            }
        }
        let SccSolver { sccs, low_link, .. } = s;
        SccResult { sccs, low_link }
    }
}

#[derive(Debug)]
pub struct SccResult {
    sccs: Vec<Vec<usize>>,
    low_link: Vec<i32>,
}

impl SccResult {
    pub fn scc_count(&self) -> usize {
        self.sccs.len()
    }
    pub fn in_same_scc(&self, nodes: &[usize]) -> bool {
        let id = self.low_link[nodes[0]];
        nodes.iter().all(|&node| self.low_link[node] == id)
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_tarjan_scc() {
        let graph = UnweightedAdjacencyList::new_directed(
            10,
            &[
                // SCC 1 with nodes 0,1,2
                [0, 1],
                [1, 2],
                [2, 0],
                // SCC 2 with nodes 3,4,5,6
                [5, 4],
                [5, 6],
                [3, 5],
                [4, 3],
                [4, 5],
                [6, 4],
                // SCC 3 with nodes 7,8
                [7, 8],
                [8, 7],
                // SCC 4 is node 9 all alone by itself
                // Add a few more edges to make things interesting
                [1, 5],
                [1, 7],
                [2, 7],
                [6, 8],
                [9, 8],
                [9, 4],
            ],
        );
        let res = graph.scc();
        assert_eq!(res.scc_count(), 4);
        assert!(res.in_same_scc(&[0, 1, 2]));
        assert!(res.in_same_scc(&[3, 4, 5, 6]));
        assert!(res.in_same_scc(&[7, 8]));
        assert!(res.in_same_scc(&[9]));
        // not in the same scc
        assert!(!res.in_same_scc(&[8, 9]));
    }
}