Java solution using Topological Sort: similar to alien dictionary


  • 0
    S
    public class Solution {
        
        public int[] findOrder(int numCourses, int[][] prerequisites) {
            
            Map<Integer, Set<Integer>> graph = new HashMap<>();
            
            //build graph
            for(int[] edge : prerequisites) {
                buildGraph(graph, edge[0], edge[1]);
            }
            // add all remaining vertices
            for(int vertex = 0 ; vertex < numCourses; vertex++)
                buildGraph(graph, vertex, -1);  // -1 indicates no edge
            
            
            //perform topological sort
            Set<Integer> visited = new HashSet<>();
            Set<Integer> visiting = new HashSet<>();
            Stack<Integer> res = new Stack<Integer>();
            for(int node: graph.keySet()) {
                if(visited.contains(node)) {
                    continue;
                }
                if(!DFS(graph, node, visited, visiting, res)) {
                    return new int[0];
                }
            }
            int[] result = new int[numCourses];
            for(int i = numCourses-1; i >= 0 && !res.isEmpty(); i--) 
                result[i] = res.pop();
            
            return result;
        }
        
        
        public void buildGraph(Map<Integer, Set<Integer>> graph, int start, int end) {
            graph.putIfAbsent(start, new HashSet<Integer>());
            if(end != -1) graph.get(start).add(end);
        }
        
        public boolean DFS(Map<Integer, Set<Integer>> graph, Integer root, Set<Integer> visited, Set<Integer> visiting, Stack<Integer> res) {
            if(visiting.contains(root)) return false;
            
            // Visit children first before visiting parent
            Set<Integer> children = graph.get(root);
            if(children != null) {
                visiting.add(root);
                for(int child: children) {
                    if(visited.contains(child)) continue;
                    if(!DFS(graph, child, visited, visiting, res)) return false;
                }
            }
            
            //now visit parent
            visited.add(root);
            visiting.remove(root);
            res.push(root);
            return true;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.