207. Course Schedule

問題文

prerequisites[i] = [a, b]
a : second
b : first

例

Input:
  numCourses = 2
  prerequisites = [[1,0],[0,1]]
  
Output:
  false
  
Explanation:
  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.

CODE

def canFinish(numCourses, prerequisites):

    # requirement：履修順番
    requirement = collections.defaultdict(list)
    for second, first in prerequisites:
        requirement[first].append(second)

    course_state = ['not-ckecked' for _ in range(numCourses)]

    # サイクルになっている場合　： True
    # サイクルになっていない場合： False
    def hasCycle(course_index):
        if course_state[course_index] == 'checking':
            return True

        if course_state[course_index] == 'no-problem':
            return False

        course_state[course_index] = 'checking'

        for next_course_index in requirement[course_index]:
            if hasCycle(next_course_index):
                return True
            
        course_state[course_index] = 'no-problem'
        return False

    for course_index in range(numCourses):
        if hasCycle(course_index):
            return False
            
    return True