LeetCode Link

BFS with indegrees

public boolean canFinish(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);
                }
            }  
        }
    }
    
    return completedCourses.size() == numCourses;
}

DFS

public boolean canFinish(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];
    
    for (int i = 0; i < numCourses; i++) {
        if (!dfs(i, visiting, visited, map)) {
            return false;
        }
    }
    
    return true;
}

// graph has no cycle
private boolean dfs(int course, boolean[] visiting, boolean[] visited, 
        Map<Integer, List<Integer>> map) {
    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)) {
                return false;
            }
        }
    }
    visiting[course] = false;
    visited[course] = true;
    
    return true;
}