Last active
October 19, 2023 06:29
-
-
Save MikuroXina/d4cc6d0231871bb17a824d3202e4a432 to your computer and use it in GitHub Desktop.
An implementation of extracting strongly connected components with Rust.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
pub fn strongly_connected_components(graph: &[Vec<usize>]) -> Vec<Vec<usize>> { | |
let vertexes = graph.len(); | |
let inv_graph = { | |
let mut inv_graph = vec![vec![]; vertexes]; | |
for (from, adj) in graph.into_iter().enumerate() { | |
for &to in adj { | |
inv_graph[to].push(from); | |
} | |
} | |
inv_graph | |
}; | |
let dead_end_vertexes = { | |
let mut visited = vec![false; vertexes]; | |
let mut dead_end_vertexes = Vec::with_capacity(vertexes); | |
for start in 0..vertexes { | |
if visited[start] { | |
continue; | |
} | |
fn dfs( | |
graph: &[Vec<usize>], | |
current: usize, | |
visited: &mut [bool], | |
dead_end_vertexes: &mut Vec<usize>, | |
) { | |
visited[current] = true; | |
for &next in &graph[current] { | |
if !visited[next] { | |
dfs(graph, next, visited, dead_end_vertexes); | |
} | |
} | |
dead_end_vertexes.push(current); | |
} | |
dfs(graph, start, &mut visited, &mut dead_end_vertexes); | |
} | |
dead_end_vertexes | |
}; | |
{ | |
let mut scc = vec![]; | |
let mut visited = vec![false; vertexes]; | |
for start in dead_end_vertexes.into_iter().rev() { | |
if visited[start] { | |
continue; | |
} | |
let mut group = vec![]; | |
fn dfs( | |
inv_graph: &[Vec<usize>], | |
current: usize, | |
visited: &mut [bool], | |
group: &mut Vec<usize>, | |
) { | |
visited[current] = true; | |
group.push(current); | |
for &next in &inv_graph[current] { | |
if !visited[next] { | |
dfs(inv_graph, next, visited, group); | |
} | |
} | |
} | |
dfs(&inv_graph, start, &mut visited, &mut group); | |
scc.push(group); | |
} | |
scc | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment