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); | |
| } | |