courseSchedule.py

# 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.


class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """
        visited = [False] * numCourses
        checked = [False] * numCourses
        mypreq = {}
        for k,v in prerequisites:
            mypreq[k] = mypreq.get(k, []) + [v]

        def DFS(k):
            if checked[k]:
                return True
            if visited[k]:
                return False
            visited[k] = True
            finishable = True
            for p in mypreq.get(k,[]):
                finishable = finishable and DFS(p)
            if finishable:
                checked[k] = True
                return True
            else:
                return False

        for i in range(numCourses):
            if not DFS(i):
                return False
        return True