# Course Schedule

## Intuition

1. Course Schedule

The problem equals to judge whether the graph have loop.

## Solution

``````
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:
requisites[a].append(b)
# 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]:
continue
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

``````