Spaces:
Runtime error
Runtime error
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); | |
} | |