Skip to content

Instantly share code, notes, and snippets.

@MikuroXina
Last active October 19, 2023 06:29
Show Gist options
  • Save MikuroXina/d4cc6d0231871bb17a824d3202e4a432 to your computer and use it in GitHub Desktop.
Save MikuroXina/d4cc6d0231871bb17a824d3202e4a432 to your computer and use it in GitHub Desktop.
An implementation of extracting strongly connected components with Rust.
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