ac_library/
scc.rs

1//! A `SccGraph` is a directed graph that calculates strongly connected components (SCC) in $O(|V| + |E|)$.
2
3use crate::internal_scc;
4
5/// An `SccGraph` is a directed graph that calculates strongly connected components (SCC) in $O(|V| + |E|)$.
6///
7/// # Example
8///
9/// ```
10/// use ac_library::SccGraph;
11/// use proconio::{input, source::once::OnceSource};
12///
13/// input! {
14///     from OnceSource::from(
15///         "5\n\
16///          5\n\
17///          0 1\n\
18///          1 2\n\
19///          2 0\n\
20///          0 3\n\
21///          3 4\n",
22///     ),
23///     n: usize,
24///     abs: [(usize, usize)],
25/// }
26///
27/// let mut graph = SccGraph::new(n);
28/// for (a, b) in abs {
29///     graph.add_edge(a, b);
30/// }
31///
32/// assert_eq!(graph.scc(), [&[0, 1, 2][..], &[3], &[4]]);
33/// ```
34#[derive(Clone, Debug)]
35pub struct SccGraph {
36    internal: internal_scc::SccGraph,
37}
38
39impl SccGraph {
40    /// Creates a new `SccGraph` with `n` vertices and `0` edges.
41    ///
42    /// # Constraints
43    ///
44    /// - $0 \leq n \leq 10^8$
45    ///
46    /// # Complexity
47    ///
48    /// - $O(n)$
49    pub fn new(n: usize) -> Self {
50        SccGraph {
51            internal: internal_scc::SccGraph::new(n),
52        }
53    }
54
55    /// Adds a directed edge from the vertex `from` to the vertex `to`.
56    ///
57    /// # Constraints
58    ///
59    /// - $0 \leq$ `from` $< n$
60    /// - $0 \leq$ `to` $< n$
61    ///
62    /// # Panics
63    ///
64    /// Panics if the above constraints are not satisfied.
65    ///
66    /// # Complexity
67    ///
68    /// - $O(1)$ amortized
69    pub fn add_edge(&mut self, from: usize, to: usize) {
70        let n = self.internal.num_vertices();
71        assert!(from < n);
72        assert!(to < n);
73        self.internal.add_edge(from, to);
74    }
75
76    /// Calculates the strongly connected components (SCC) of directed graphs in $O(|V| + |E|)$.
77    ///
78    /// Returns the list of the "list of the vertices" that satisfies the following.
79    ///
80    /// - Each vertex is in exactly one "list of the vertices".
81    /// - Each "list of the vertices" corresponds to the vertex set of a strongly connected component. The order of the vertices in the list is undefined.
82    /// - The list of "list of the vertices" are sorted in topological order, i.e., for two vertices $u$, $v$ in different strongly connected components, if there is a directed path from $u$ to $v$, the list containing $u$ appears earlier than the list containing $v$.
83    ///
84    /// # Complexity
85    ///
86    /// - $O(n + m)$ where $m$ is the number of added edges
87    pub fn scc(&self) -> Vec<Vec<usize>> {
88        self.internal.scc()
89    }
90}
91
92#[cfg(test)]
93mod tests {
94    use super::*;
95
96    #[test]
97    fn test_scc_simple() {
98        let mut graph = SccGraph::new(2);
99        graph.add_edge(0, 1);
100        graph.add_edge(1, 0);
101        let scc = graph.scc();
102        assert_eq!(scc.len(), 1);
103    }
104
105    #[test]
106    fn test_scc_self_loop() {
107        let mut graph = SccGraph::new(2);
108        graph.add_edge(0, 0);
109        graph.add_edge(0, 0);
110        graph.add_edge(1, 1);
111        let scc = graph.scc();
112        assert_eq!(scc.len(), 2);
113    }
114
115    #[test]
116    fn solve_alpc_g_sample1() {
117        // https://atcoder.jp/contests/practice2/tasks/practice2_g
118        let n: usize = 6;
119        let edges = vec![(1, 4), (5, 2), (3, 0), (5, 5), (4, 1), (0, 3), (4, 2)];
120
121        let mut graph = SccGraph::new(n);
122        for (u, v) in edges.into_iter() {
123            graph.add_edge(u, v);
124        }
125
126        let scc = graph.scc();
127        assert_eq!(scc, vec![vec![5], vec![1, 4], vec![2], vec![0, 3]]);
128    }
129}
ac_library/scc.rs

ac_library/
scc.rs
