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 prerequisitepairs, 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:

Time Complexity: O(V + E) where V is number of classes, E is the pre-requisite classes from each class

The basic solution idea is topological sort. If there exists a cycle in this DAG, then topological sort cannot work and there exists a circular pre-requisite course loop that won't allow this student to finish courses.

1. create a hashmap to store each course as key, the pre-requisites of this course as values
2. Create a set "taken" to avoid taking same class again.
3. For each courseKey in hashMap,
   1. dfs_take this class, passing in its ancestors stack to keep track which course leads us to take this class
   2. the result of dfs_take should be boolean, with 'false' indicating there is a cycle or backward edge in the recursion
   3. if res == true, add the courseKey to set taken
4. return true

class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """

        # create a map<course, pre-request courses>
        # O(n) where n = numCourses
        dic = {}
        for i in range(numCourses):
            dic[i] = []
        for [x,y] in prerequisites:
            dic[x].append(y)

        print dic
        # run dfs thru the course. Also keep track of tree edges.
        taken = set() # is a set of taken classes to avoid duplicates
        for courseKey in dic:
            if courseKey not in taken:
                res = self.dfsVisit(dic, courseKey, [], taken)
                if res == False:
                    return False
                taken.add(courseKey)

        # if it can run through fine, return True
        return True

    # ancestor is the processing stack, for ancestor tracking
    def dfsVisit(self, prereqDict, course, ancestors, taken):

        for prereqCourse in prereqDict[course]:
            # crucial step to determine if prereq course is in the ancestors stack. 
            # If yes, then it's a backward edge
            if prereqCourse in ancestors:
                    return False 
            if prereqCourse not in taken:
                res = self.dfsVisit(prereqDict, prereqCourse, ancestors + [prereqCourse], taken)
                if res == False:
                    return False
                taken.add(prereqCourse)
        return True