[java/8ms/14ms] straightforward DFS & BFS


  • 1

    DFS

    public int[] findOrder(int numCourses, int[][] prerequisites) {
            List<Integer> course = new LinkedList<>();
            List<Integer>[] graph = buildGraph(numCourses, prerequisites);
    
            boolean[] global = new boolean[numCourses];
            boolean[] local  = new boolean[numCourses];
            for (int i = 0; i < numCourses; i++) {
                if (!global[i] && !dfs_is_dag(graph, i, global, local, course)) {
                    return new int[0];
                }
            }
            
            int i = 0, res[] = new int[numCourses];
            for (int v : course) {
                res[i++] = v;
            }
        
            return res;
        }
    
    
        // p[0] -> p[1], reverse the relationship
        private List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
            List<Integer>[] graph = new ArrayList[numCourses];
            for (int[] p : prerequisites) {
                List<Integer> lst = graph[p[0]];
                if (lst == null) {
                    lst = new ArrayList<>();
                    graph[p[0]] = lst; 
                }
                // System.out.println(p[0] + " : " + p[1]);
                lst.add(p[1]);
            }
            return graph;
        }
    
        private boolean dfs_is_dag(List<Integer>[] graph, int v, boolean[] global, boolean[] local, 
                                   List<Integer> res) {
            // avoid checking DAG which has been validated.
            if (global[v]) return true;
            global[v] = true;
            List<Integer> lst = graph[v];
            // System.out.println(v);
            if (lst == null) {
                res.add(v);
                return true;
            }
    
            local[v] = true;
            for (int i : lst) {
                if (local[i] || !dfs_is_dag(graph, i, global, local, res))
                    return false;
            }
            local[v] = false;
            res.add(v);
            return true;
        }
    

    BFS or Khan's Algorithm

    public int[] findOrder(int numCourses, int[][] prerequisites) {
            List<Integer>[] graph = buildGraph(numCourses, prerequisites);
            int[] res = new int[numCourses];
            int pos = numCourses;
            
            int[] indegree = bfs_indegree(numCourses, prerequisites);
            for (int i = 0; i < numCourses; i++) {
                int j = 0;
                for (; j < numCourses; j++) {
                    if (indegree[j] == 0) break;
                }
                if (j == numCourses) return new int[0];
                indegree[j] = -1;
                List<Integer> lst = graph[j];
                res[--pos] = j;
                if (lst != null) {
                    for (int v : lst) {
                        --indegree[v];
                    }
                }
            }
    
            return res;
        }
        
        private List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
            List<Integer>[] graph = new ArrayList[numCourses];
            for (int[] p : prerequisites) {
                List<Integer> lst = graph[p[0]];
                if (lst == null) {
                    lst = new ArrayList<>();
                    graph[p[0]] = lst;
                }
                lst.add(p[1]);
            }
            return graph;
        }
    
        private int[] bfs_indegree(int vertices, int[][] edges) {
            int[] indegree = new int[vertices];
            for (int[] edge : edges) {
                indegree[edge[1]]++;
            }
            return indegree;
        }
    

Log in to reply
 

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