use std::collections::{BTreeSet, HashMap, HashSet};
use std::hash::Hash;

/// Compute the strongly connected components of a directed graph using
/// Tarjan's algorithm.
///
/// `nodes` is the full vertex set (vertices not in `successors` are treated as
/// having no outgoing edges). Edges to vertices outside `nodes` are ignored.
///
/// Returns SCCs in **reverse topological order** (leaf/sink components first).
/// Callers that need topological order should reverse the result.
///
/// # Complexity
///
/// O(V + E) time and space, where V = `nodes.len()` and E is the total number
/// of edges in `successors`.
///
/// # References
///
/// Tarjan, R. E. (1972). *Depth-first search and linear graph algorithms*.
/// SIAM Journal on Computing, 1(2), 146--160.
pub fn strongly_connected_components<N>(
    nodes: &BTreeSet<N>,
    successors: &HashMap<N, Vec<N>>,
) -> Vec<BTreeSet<N>>
where
    N: Copy + Eq + Hash + Ord,
{
    let mut state = TarjanState {
        index_counter: 0,
        stack: Vec::new(),
        on_stack: HashSet::new(),
        indices: HashMap::new(),
        lowlinks: HashMap::new(),
        result: Vec::new(),
    };

    for &node in nodes {
        if !state.indices.contains_key(&node) {
            state.dfs(node, successors, nodes);
        }
    }

    state.result
}

struct TarjanState<N> {
    index_counter: usize,
    stack: Vec<N>,
    on_stack: HashSet<N>,
    indices: HashMap<N, usize>,
    lowlinks: HashMap<N, usize>,
    result: Vec<BTreeSet<N>>,
}

impl<N: Copy + Eq + Hash + Ord> TarjanState<N> {
    fn dfs(&mut self, v: N, successors: &HashMap<N, Vec<N>>, all_nodes: &BTreeSet<N>) {
        self.indices.insert(v, self.index_counter);
        self.lowlinks.insert(v, self.index_counter);
        self.index_counter += 1;
        self.stack.push(v);
        self.on_stack.insert(v);

        if let Some(neighbours) = successors.get(&v) {
            for &w in neighbours {
                if !all_nodes.contains(&w) {
                    continue;
                }
                if !self.indices.contains_key(&w) {
                    self.dfs(w, successors, all_nodes);
                    let w_low = self.lowlinks[&w];
                    let v_low = self.lowlinks.get_mut(&v).unwrap();
                    if w_low < *v_low {
                        *v_low = w_low;
                    }
                } else if self.on_stack.contains(&w) {
                    let w_idx = self.indices[&w];
                    let v_low = self.lowlinks.get_mut(&v).unwrap();
                    if w_idx < *v_low {
                        *v_low = w_idx;
                    }
                }
            }
        }

        if self.lowlinks[&v] == self.indices[&v] {
            let mut component = BTreeSet::new();
            loop {
                let w = self.stack.pop().unwrap();
                self.on_stack.remove(&w);
                component.insert(w);
                if w == v {
                    break;
                }
            }
            self.result.push(component);
        }
    }
}
