Spaces:
Runtime error
Runtime error
File size: 1,053 Bytes
6118d1d |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
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); } |