use std::collections::{HashSet, VecDeque};

fn topological_sort(graph: &Vec<Vec<usize>>) -> Vec<usize> {
    let mut visited = HashSet::new();
    let mut stack = VecDeque::new();
    let mut result = Vec::new();

    for node in 0..graph.len() {
        if !visited.contains(&node) {
            dfs(node, graph, &mut visited, &mut stack);
        }
    }

    while let Some(node) = stack.pop_front() {
        result.push(node);
    }

    result
}

fn dfs(node: usize, graph: &Vec<Vec<usize>>, visited: &mut HashSet<usize>, stack: &mut VecDeque<usize>) {
    visited.insert(node);

    for &neighbor in &graph[node] {
        if !visited.contains(&neighbor) {
            dfs(neighbor, graph, visited, stack);
        }
    }

    stack.push_front(node);
}

fn main() {
    // Example graph with 6 nodes and 7 edges
    let graph = vec![
        vec![1, 2],
        vec![3],
        vec![3, 4],
        vec![4, 5],
        vec![],
        vec![],
    ];

    let sorted = topological_sort(&graph);

    println!("Topological sort: {:?}", sorted);
}