207.Course Schedule

There are a total ofncourses you have to take, labeled from0ton - 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:

1. The input prerequisites is a graph represented by a list of edges , not adjacency matrices. Read more about how a graph is represented.
2. You may assume that there are no duplicate edges in the input prerequisites.

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

Analysis:

Need to learn Topological Sort first before solve this question.

Kahn's Algorithm:

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
    remove a node n from S
    add n to tail of L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    return error (graph has at least one cycle)
else 
    return L (a topologically sorted order)

Basically, to traverse a directed graph in topological order, strategy is:

1. find all node that inDgree is zero (only connect OUT to other nodes), put them in a queue
2. BFS all elements in queue, for each touched neighbors, decrease their inDegree, when inDegree reach ZERO. Add that node into queue.(Sort of like prerequisite for that node is all granted, so ready to be traversed)
3. keep doing this until queue is empty. If there are still nodes with inDegree != 0, circle exists.

Code:

public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if(numCourses <= 1 || prerequisites == null || prerequisites.length == 0)
        {
            return true;
        }

        //build Graph 
        List<List<Integer>> graph = new ArrayList<List<Integer>>(numCourses);
        int[] inD = new int[numCourses];
        int inDegree = 0;
        for(int i = 0; i<numCourses; i++)
        {
            graph.add(new LinkedList<Integer>());
        }

        for(int[] edge : prerequisites)
        {
            graph.get(edge[0]).add(edge[1]);
            inD[edge[1]]++;
            inDegree++;
        }

        Deque<Integer> queue = new LinkedList<Integer>();
        for(int i = 0; i < numCourses; i++)
        {
            if(inD[i] == 0)
            {
                queue.add(i);
            }
        }

        while(!queue.isEmpty())
        {
            for(Integer itr : graph.get(queue.poll()))
            {
                inD[itr]--;
                inDegree--;
                if(inD[itr] == 0)
                {
                    queue.offer(itr);
                }
            }
        }

        return inDegree == 0;
    }
}