use std::collections::{BTreeMap, BTreeSet};
pub fn tarjan_scc(nodes: &[String], adj: &BTreeMap<String, BTreeSet<String>>) -> Vec<Vec<String>> {
struct TarjanState<'a> {
index: usize,
indices: BTreeMap<String, usize>,
lowlink: BTreeMap<String, usize>,
stack: Vec<String>,
on_stack: BTreeSet<String>,
sccs: Vec<Vec<String>>,
adj: &'a BTreeMap<String, BTreeSet<String>>,
}
fn strongconnect(v: &str, st: &mut TarjanState<'_>) {
let cur = st.index;
st.indices.insert(v.to_string(), cur);
st.lowlink.insert(v.to_string(), cur);
st.index += 1;
st.stack.push(v.to_string());
st.on_stack.insert(v.to_string());
if let Some(nbrs) = st.adj.get(v) {
for w in nbrs {
if !st.indices.contains_key(w) {
strongconnect(w, st);
let (lw, lv) = (st.lowlink[w], st.lowlink[v]);
if lw < lv { st.lowlink.insert(v.to_string(), lw); }
} else if st.on_stack.contains(w) {
let (iw, lv) = (st.indices[w], st.lowlink[v]);
if iw < lv { st.lowlink.insert(v.to_string(), iw); }
}
}
}
if st.lowlink[v] == st.indices[v] {
let mut comp = Vec::new();
while let Some(w) = st.stack.pop() {
st.on_stack.remove(&w);
let done = w == v;
comp.push(w);
if done { break; }
}
comp.sort();
st.sccs.push(comp);
}
}
let mut sorted_nodes = nodes.to_vec();
sorted_nodes.sort();
let mut state = TarjanState {
index: 0, indices: BTreeMap::new(), lowlink: BTreeMap::new(),
stack: Vec::new(), on_stack: BTreeSet::new(), sccs: Vec::new(), adj,
};
for n in &sorted_nodes {
if !state.indices.contains_key(n) { strongconnect(n, &mut state); }
}
state.sccs.reverse();
state.sccs
}