Course Schedule

Problem Id: 207 Difficulty: Medium


  1. Course Schedule

The problem equals to judge whether the graph have loop.


from collections import defaultdict
class Solution:
    def canFinish(self, numCourses, prerequisites):
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        requisites = defaultdict(list)
        for a, b in prerequisites:
        # Skip taken_course
        taken_course = [False] * numCourses

        def dfs(course):
            """Whether the graph has loop dfs from point *course*"""
            if taken_course[course]:
                return True

            if course in visited:
                return False

            for req in requisites[course]:
                if taken_course[req]:
                if not dfs(req):
                    return False

            taken_course[course] = True
            return True

        for course in range(numCourses):
            visited = set()     # Visited in this traversing
            if not dfs(course):
                return False

        return True

if __name__ == '__main__':
    from sample import cases
    for args, result in cases:
        print("Running with case:", args, result)
        assert Solution().canFinish(*args) == result