competitive/graph/
strongly_connected_component.rs

1use super::DirectedSparseGraph;
2
3#[derive(Debug, Clone)]
4pub struct StronglyConnectedComponent<'a> {
5    graph: &'a DirectedSparseGraph,
6    visited: Vec<usize>,
7    csize: usize,
8    low: Vec<usize>,
9    ord: Vec<usize>,
10    comp: Vec<usize>,
11}
12impl std::ops::Index<usize> for StronglyConnectedComponent<'_> {
13    type Output = usize;
14    fn index(&self, index: usize) -> &Self::Output {
15        &self.comp[index]
16    }
17}
18impl<'a> StronglyConnectedComponent<'a> {
19    pub fn new(graph: &'a DirectedSparseGraph) -> Self {
20        let mut now_ord = 0;
21        let mut self_ = Self {
22            graph,
23            csize: 0,
24            visited: Vec::with_capacity(graph.vertices_size()),
25            low: vec![0; graph.vertices_size()],
26            ord: vec![usize::MAX; graph.vertices_size()],
27            comp: vec![0; graph.vertices_size()],
28        };
29        for u in graph.vertices() {
30            if self_.ord[u] == usize::MAX {
31                self_.dfs(u, &mut now_ord);
32            }
33        }
34        for x in self_.comp.iter_mut() {
35            *x = self_.csize - 1 - *x;
36        }
37        self_
38    }
39}
40impl StronglyConnectedComponent<'_> {
41    fn dfs(&mut self, u: usize, now_ord: &mut usize) {
42        self.low[u] = *now_ord;
43        self.ord[u] = *now_ord;
44        *now_ord += 1;
45        self.visited.push(u);
46        for a in self.graph.adjacencies(u) {
47            if self.ord[a.to] == usize::MAX {
48                self.dfs(a.to, now_ord);
49                self.low[u] = self.low[u].min(self.low[a.to]);
50            } else {
51                self.low[u] = self.low[u].min(self.ord[a.to]);
52            }
53        }
54        if self.low[u] == self.ord[u] {
55            while let Some(v) = self.visited.pop() {
56                self.ord[v] = self.graph.vertices_size();
57                self.comp[v] = self.csize;
58                if v == u {
59                    break;
60                }
61            }
62            self.csize += 1;
63        }
64    }
65    pub fn gen_cgraph(&self) -> DirectedSparseGraph {
66        let mut used = std::collections::HashSet::new();
67        let mut edges = vec![];
68        for u in self.graph.vertices() {
69            for a in self.graph.adjacencies(u) {
70                if self.comp[u] != self.comp[a.to] {
71                    let (x, y) = (self.comp[u], self.comp[a.to]);
72                    if !used.contains(&(x, y)) {
73                        used.insert((x, y));
74                        edges.push((x, y));
75                    }
76                }
77            }
78        }
79        DirectedSparseGraph::from_edges(self.size(), edges)
80    }
81    pub fn components(&self) -> Vec<Vec<usize>> {
82        let mut counts = vec![0; self.size()];
83        for &x in self.comp.iter() {
84            counts[x] += 1;
85        }
86        let mut groups = vec![vec![]; self.size()];
87        for (g, c) in groups.iter_mut().zip(counts.into_iter()) {
88            g.reserve(c);
89        }
90        for u in self.graph.vertices() {
91            groups[self[u]].push(u);
92        }
93        groups
94    }
95    pub fn has_loop(&self) -> bool {
96        self.graph.vertices_size() != self.csize
97    }
98    pub fn size(&self) -> usize {
99        self.csize
100    }
101}
competitive/graph/strongly_connected_component.rs

competitive/graph/
strongly_connected_component.rs
