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

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.

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:

This is a graph problem which is basically to check if there are cycles. 

The brute force of checking cycle is to DFS all the vertices and check all the paths, see if it contains duplicate vertices in the path.  It will not pass the OJ due to the time.

Couple observations:

Basic idea: if there exists a cycle in the graph, all the nodes in this cycles will have positive out degrees, which in this case means they must have at least one prerequisite course that we cannot resolve.

If a vertex doesn't have any outgoing edge, we can finish this course, because it don't possess any prerequisite course.

We can start from those courses and BFS the graph, reduce the out degree of those courses that depend on the finished courses, check if we can finish the course by checking its out degree. 

 public boolean canFinish(int numCourses, int[][] prerequisites) {  
     int[] od=new int[numCourses];  
     int n=prerequisites.length;  
     List<List<Integer>> dependencies=new ArrayList<List<Integer>>();  
     for(int i=0;i<numCourses;i++){  
       dependencies.add(new ArrayList<Integer>());  
     }  
     for(int i=0;i<n;i++){  
       od[prerequisites[i][0]]++;  
       dependencies.get(prerequisites[i][1]).add(prerequisites[i][0]);  
     }  
     LinkedList<Integer> q=new LinkedList<Integer>();  
     int canFinishedCourse=0;  
     for(int i=0;i<numCourses;i++){  
       if(od[i]==0){  
         canFinishedCourse++;  
         q.offer(i);  
       }  
     }  
     while(!q.isEmpty()){  
       int cur=q.poll();  
         List<Integer> allDepCourses=dependencies.get(cur);  
         for(int i:allDepCourses){  
           od[i]--;  
           if(od[i]==0){  
             q.offer(i);  
             canFinishedCourse++;  
           }  
         }  
     }  
     return canFinishedCourse==numCourses;  
   }