[LeetCode] Course Schedule

Course Schedule

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

click to show more hints.

Hints:

1. This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
2. Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
3. Topological sort could also be done via BFS.

Solution: We keep track of vertices currently in recursion stack of function for DFS traversal. If a vertex is encountered again, then there is a cycle.
Furthermore, we keep track of nodes that have been the root for DFS traversal, to avoid duplicate testing, and more importantly, infinite loop.

public class Solution {
    ArrayList<ArrayList<Integer>> list;
    
    public boolean DFS(int i, boolean[] visited, boolean[] recStack) {
        visited[i] = true;
        recStack[i] = true;
        for (int j : list.get(i)) {
            if (recStack[j]) {
                return false;
            }
            if (!visited[j] && !DFS(j, visited, recStack)) {
                return false;
            }
        }
        recStack[i] = false;
        return true;
    }
    
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int n = numCourses;
        list = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i < n; i++) {
            list.add(new ArrayList<Integer>());
        }
        for (int[] pair : prerequisites) {
            list.get(pair[1]).add(pair[0]);
        }
        boolean[] visited = new boolean[n];
        boolean[] recStack = new boolean[n];
        Arrays.fill(visited, false);
        Arrays.fill(recStack, false);
        for (int i = 0; i < n; i++) {
            if (!visited[i] && !DFS(i, visited, recStack)) {
                return false;
            }
        }
        return true;
    }
}