(graph: &dyn IGraph)
| 17 | |
| 18 | impl KosarajuSCC { |
| 19 | pub fn new(graph: &dyn IGraph) -> Self { |
| 20 | let mut scc = Self { |
| 21 | marked: vec![false; graph.V()], |
| 22 | id: vec![0; graph.V()], |
| 23 | count: 0, |
| 24 | }; |
| 25 | let order = DepthFirstOrders::from(graph.reverse().as_ref()); |
| 26 | for &s in order.rev_post() { |
| 27 | if !scc.marked[s] { |
| 28 | scc.dfs(graph, s); |
| 29 | scc.count += 1; |
| 30 | } |
| 31 | } |
| 32 | |
| 33 | scc |
| 34 | } |
| 35 | |
| 36 | pub fn strongly_connected(&self, v: usize, w: usize) -> bool { |
| 37 | self.id[v] == self.id[w] |