Strongly Connected Components
Finding SCCs of a directed graph. Tarjan's algorithm is used for the algorithm.
Example
use scc::*; fn main() { let mut graph = vec![vec![]; 5]; for (u, v) in [(0, 2), (3, 0), (2, 3), (0, 1), (1, 4)] { graph[u].push(v); } let scc_list = find_scc(&graph); println!("{:?}", scc_list); // [[3, 2, 0], [1], [4]] let scc_id = gen_scc_ids(&graph, &scc_list); println!("{:?}", scc_id); // [0, 1, 0, 0, 2] let scc_graph = gen_scc_graph(&graph, &scc_list, &scc_id); println!("{:?}", scc_graph); // [[1], [2], []] } mod scc { struct SccStack { stack: Vec<u32>, check: Vec<u64>, } impl SccStack { fn new(cap: usize) -> Self { Self { stack: vec![0; cap], check: vec![0; (cap + 63) / 64], } } fn push(&mut self, n: usize) { self.stack.push(n as u32); self.check[n / 64] |= 1 << (n % 64); } fn pop(&mut self) -> Option<usize> { let tmp = self.stack.pop()? as usize; self.check[tmp / 64] &= !(1 << (tmp % 64)); Some(tmp) } fn contains(&self, n: usize) -> bool { self.check[n / 64] & (1 << (n % 64)) != 0 } } struct DfsPack { gid: usize, id: Vec<usize>, low: Vec<usize>, st: SccStack, } fn dfs(n: usize, graph: &[Vec<usize>], curr: usize, p: &mut DfsPack, list: &mut Vec<Vec<usize>>) { p.st.push(curr); p.id[curr] = p.gid; p.low[curr] = p.gid; p.gid += 1; for &next in graph[curr].iter() { if p.id[next] == n { dfs(n, graph, next, p, list); } } for &next in graph[curr].iter() { if p.st.contains(next) { p.low[curr] = p.low[curr].min(p.low[next]); } } if p.id[curr] == p.low[curr] { let mut newlist = vec![]; while let Some(popped) = p.st.pop() { if popped == curr { break; } newlist.push(popped); } newlist.push(curr); list.push(newlist); } } /// Returns a list of SCCs of `graph`. /// The returned list is a 2D vector of `usize`, which consists of a list of vertices within a same SCC. /// The order of the SCCs in the returned list is topologically sorted. /// /// The implementation uses Tarjan's SCC algorithm. pub fn find_scc(graph: &[Vec<usize>]) -> Vec<Vec<usize>> { let n = graph.len(); let mut list = vec![]; let mut p = DfsPack { gid: 0, id: vec![n; n], low: vec![usize::MAX; n], st: SccStack::new(n), }; for x in 0..n { if p.id[x] != n { continue; } dfs(n, graph, x, &mut p, &mut list); } list.reverse(); list } /// Returns a list about what SCC each vertices are in. /// `scc_list` has to be generated in advance from `find_scc`. pub fn gen_scc_ids(graph: &[Vec<usize>], scc_list: &[Vec<usize>]) -> Vec<usize> { let mut ids = vec![0; graph.len()]; for (i, l) in scc_list.iter().enumerate() { for &v in l { ids[v] = i; } } ids } /// Returns a graph of SCCs. The number of vertices of the new graph will be the number of SCCs in the graph. /// `scc_list` and `scc_ids` have to be generated in advanced from `find_scc` and `gen_scc_ids`. pub fn gen_scc_graph(graph: &[Vec<usize>], scc_list: &[Vec<usize>], scc_ids: &[usize]) -> Vec<Vec<usize>> { let mut ret = vec![vec![]; scc_list.len()]; for u in 0..graph.len() { let a = scc_ids[u]; for &v in graph[u].iter() { let b = scc_ids[v]; if a < b { ret[a].push(b); } } } ret } }
Code
mod scc {
struct SccStack {
stack: Vec<u32>,
check: Vec<u64>,
}
impl SccStack {
fn new(cap: usize) -> Self {
Self {
stack: vec![0; cap],
check: vec![0; (cap + 63) / 64],
}
}
fn push(&mut self, n: usize) {
self.stack.push(n as u32);
self.check[n / 64] |= 1 << (n % 64);
}
fn pop(&mut self) -> Option<usize> {
let tmp = self.stack.pop()? as usize;
self.check[tmp / 64] &= !(1 << (tmp % 64));
Some(tmp)
}
fn contains(&self, n: usize) -> bool {
self.check[n / 64] & (1 << (n % 64)) != 0
}
}
struct DfsPack {
gid: usize,
id: Vec<usize>,
low: Vec<usize>,
st: SccStack,
}
fn dfs(n: usize, graph: &[Vec<usize>], curr: usize, p: &mut DfsPack, list: &mut Vec<Vec<usize>>) {
p.st.push(curr);
p.id[curr] = p.gid;
p.low[curr] = p.gid;
p.gid += 1;
for &next in graph[curr].iter() {
if p.id[next] == n {
dfs(n, graph, next, p, list);
}
}
for &next in graph[curr].iter() {
if p.st.contains(next) {
p.low[curr] = p.low[curr].min(p.low[next]);
}
}
if p.id[curr] == p.low[curr] {
let mut newlist = vec![];
while let Some(popped) = p.st.pop() {
if popped == curr {
break;
}
newlist.push(popped);
}
newlist.push(curr);
list.push(newlist);
}
}
/// Returns a list of SCCs of `graph`.
/// The returned list is a 2D vector of `usize`, which consists of a list of vertices within a same SCC.
/// The order of the SCCs in the returned list is topologically sorted.
///
/// The implementation uses Tarjan's SCC algorithm.
pub fn find_scc(graph: &[Vec<usize>]) -> Vec<Vec<usize>> {
let n = graph.len();
let mut list = vec![];
let mut p = DfsPack {
gid: 0,
id: vec![n; n],
low: vec![usize::MAX; n],
st: SccStack::new(n),
};
for x in 0..n {
if p.id[x] != n {
continue;
}
dfs(n, graph, x, &mut p, &mut list);
}
list.reverse();
list
}
/// Returns a list about what SCC each vertices are in.
/// `scc_list` has to be generated in advance from `find_scc`.
pub fn gen_scc_ids(graph: &[Vec<usize>], scc_list: &[Vec<usize>]) -> Vec<usize> {
let mut ids = vec![0; graph.len()];
for (i, l) in scc_list.iter().enumerate() {
for &v in l {
ids[v] = i;
}
}
ids
}
/// Returns a graph of SCCs. The number of vertices of the new graph will be the number of SCCs in the graph.
/// `scc_list` and `scc_ids` have to be generated in advanced from `find_scc` and `gen_scc_ids`.
pub fn gen_scc_graph(graph: &[Vec<usize>], scc_list: &[Vec<usize>], scc_ids: &[usize]) -> Vec<Vec<usize>> {
let mut ret = vec![vec![]; scc_list.len()];
for u in 0..graph.len() {
let a = scc_ids[u];
for &v in graph[u].iter() {
let b = scc_ids[v];
if a < b {
ret[a].push(b);
}
}
}
ret
}
}
Last modified on 231008.