LeetCode Link

BFS with indegrees

public int[] findOrder2(int numCourses, int[][] prerequisites) {
    // prev course => next courses
    Map<Integer, List<Integer>> map = new HashMap<>();
    int[] indegrees = new int[numCourses];
    
    for (int[] dependency: prerequisites) {
        int prev = dependency[1];
        int next = dependency[0];
        indegrees[next] += 1;
        if (!map.containsKey(prev)) {
            map.put(prev, new LinkedList<Integer>());
        }
        map.get(prev).add(next);
    }
    
    Queue<Integer> queue = new LinkedList<>();
    for (int course = 0; course < numCourses; course++) {
        if (indegrees[course] == 0) {
            queue.offer(course);
        }
    }
    
    List<Integer> completedCourses = new LinkedList<>();
    while (!queue.isEmpty()) {
        int course = queue.poll();
        completedCourses.add(course);
        if (map.containsKey(course)) {
            List<Integer> nextList = map.get(course);
            for (int nextCourse: nextList) {
                indegrees[nextCourse] -= 1;
                if (indegrees[nextCourse] == 0) {
                    queue.offer(nextCourse);
                }
            }  
        }
    }
    
    if (completedCourses.size() < numCourses) {
        return new int[0];
    }
    
    return copyToArray(completedCourses);
}

private int[] copyToArray(List<Integer> list) {
    int[] copy = new int[list.size()];
    for (int i = 0; i < list.size(); i++) {
        copy[i] = list.get(i);
    }
    return copy;
}

DFS

public int[] findOrder(int numCourses, int[][] prerequisites) {
    Map<Integer, List<Integer>> map = new HashMap<>();
    for (int[] dependency: prerequisites) {
        int prev = dependency[1];
        int next = dependency[0];
        if (!map.containsKey(prev)) {
            map.put(prev, new LinkedList<Integer>());
        }
        map.get(prev).add(next);
    }
    
    boolean[] visiting = new boolean[numCourses];
    boolean[] visited = new boolean[numCourses];
    LinkedList<Integer> path = new LinkedList<>();
    
    for (int i = 0; i < numCourses; i++) {
        if (!dfs(i, visiting, visited, map, path)) {
            break;
        }
    }
    
    if (path.size() < numCourses) {
        return new int[0];
    }
    return copyToArray(path);
}

// Graph has no cycle
private boolean dfs(int course, boolean[] visiting, boolean[] visited, 
                    Map<Integer, List<Integer>> map, List<Integer> path) {
    if (visited[course]) {
        return true;
    }
    if (visiting[course]) {
        return false;
    }
    
    visiting[course] = true;
    if (map.containsKey(course)) {
        List<Integer> nextCourses = map.get(course);
        for (int nextCourse: nextCourses) {
            if (!dfs(nextCourse, visiting, visited, map, path)) {
                return false;
            }
        }
    }
    visiting[course] = false;
    visited[course] = true;
    path.add(0, course);
    
    return true;
}