competitive/graph/
strongly_connected_component.rs

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

competitive/graph/
strongly_connected_component.rs
