Leetcode: 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.

Understand the problem:
The problem is equivalent to finding if a directed graph contains a circle. Thus we could use a DFS or BFS solution.

DFS Solution:
Use an array to mark if the node has been visited before. Here is a small trick to save some time. Instead of using a boolean array, we use an integer array int[] visited. 
visited = -1, means this node has been visited. 
visited = 1, means this node has been validated which does not include a circle. Thus if we saw that a node has been validated, we don't need to calculate again to find out the circle starting from this node. e.g. [0, 1] [1, 2] [2, 3] [3, 4]. For the node 0, we have already validated 2 3 and 4 do not have a circle. Thus we don't need to calculate for the node 2 3 4 again.

Code (Java):

public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (numCourses <= 0) {
            return true;
        }
        
        if (prerequisites == null || prerequisites.length == 0) {
            return true;
        }
        
        // First transform the edge list to adj. list
        Map<Integer, List<Integer>> adjList = new HashMap<>();
        for (int[] edge : prerequisites) {
            if (adjList.containsKey(edge[0])) {
                List<Integer> neighbors = adjList.get(edge[0]);
                neighbors.add(edge[1]);
                adjList.put(edge[0], neighbors);
            } else {
                List<Integer> neighbors = new ArrayList<Integer>();
                neighbors.add(edge[1]);
                adjList.put(edge[0], neighbors);
            }
        }
        
        int[] visited = new int[numCourses];
        // Check if the graph contains a circle, if yes, return false.
        for (int i = 0; i < numCourses; i++) {
            if (hasCircles(i, visited, adjList)) {
                return false;
            }
        }
        
        return true;
    }
    
    private boolean hasCircles(int vertexId, int[] visited, Map<Integer, List<Integer>> adjList) {
        if (visited[vertexId] == -1) {
            return true;
        }
        
        if (visited[vertexId] == 1) {
            return false;
        }
        
        visited[vertexId] = -1;
        
        List<Integer> neighbors = adjList.get(vertexId);
        if (neighbors != null) {
            for (int neighbor : neighbors) {
                if (hasCircles(neighbor, visited, adjList)) {
                    return true;
                }
            }
        }
        
        visited[vertexId] = 1;
        
        return false;
    }
}

Update on 4/22/19: Using topological sorting

public class Solution {
    /*
     * @param numCourses: a total of n courses
     * @param prerequisites: a list of prerequisite pairs
     * @return: true if can finish all courses or false
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // write your code here
        if (numCourses <= 0 || prerequisites == null || prerequisites.length == 0) {
            return true;
        }

        // step 1: create adjlist and in-=degree map
        //
        Map<Integer, Integer> nodeToIndegreeMap = new HashMap<>();
        Map<Integer, List<Integer>> adjList = new HashMap<>();
        
        for (int i = 0; i < numCourses; i++) {
            nodeToIndegreeMap.put(i, 0);
            adjList.put(i, new ArrayList<>());
        }

        for (int[] prerequisite : prerequisites) {
            int inDegree = nodeToIndegreeMap.get(prerequisite[1]);
            inDegree += 1;
            nodeToIndegreeMap.put(prerequisite[1], inDegree);
        }

        for (int[] prerequisite : prerequisites) {
            List<Integer> neighbors = adjList.get(prerequisite[0]);
            neighbors.add(prerequisite[1]);
            adjList.put(prerequisite[0], neighbors);
        }

        // step 2: get all nodes with indegree 0 and put into the queuue
        //
        Queue<Integer> queue = new LinkedList<>();
        int numNodes = 0;
        for (Integer key : nodeToIndegreeMap.keySet()) {
            int indegree = nodeToIndegreeMap.get(key);
            if (indegree == 0) {
                queue.offer(key);
                numNodes += 1;
            }
        }

        while (!queue.isEmpty()) {
            int curNode = queue.poll();
            for (int neighbor : adjList.get(curNode)) {
                int indegree = nodeToIndegreeMap.get(neighbor);
                indegree -= 1;
                nodeToIndegreeMap.put(neighbor, indegree);

                if (indegree == 0) {
                    queue.offer(neighbor);
                    numNodes += 1;
                }
            }
        }

        return numNodes == numCourses;
    }
}