207. Course Schedule

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

• For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

 

Solution 1. using DFS with 3 different vertex's state

class Solution:
    def __init__(self):
        self.graph = defaultdict(list)
        self.state = list()

    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        for course in prerequisites:
            precourse, postcourse = course[1], course[0]
            self.graph[precourse].append(postcourse)

        # 0 : not visited
        # 1 : be processed
        # -1 : being processed
        self.state = [0 for i in range(numCourses)]
        
        for course in range(numCourses):
            if not self.__dfs(course, numCourses):
                return False
        
        return True

    def __dfs(self, num: int, numCourses: int) -> bool:
        if self.state[num] == 1:
            return True
        if self.state[num] == -1:
            return False
        
        self.state[num] = -1
        for postCourse in self.graph[num]:
            if not self.__dfs(postCourse, numCourses):
                return False
        
        self.state[num] = 1
        return True

 

Solution2. Topology Sort

class Solution:

    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        inDegree = [0] * numCourses
        graph = defaultdict(list)
        for courses in prerequisites:
            preCourse, postCourse = courses[1], courses[0]
            graph[preCourse].append(postCourse)
            inDegree[postCourse] += 1

        queue = list()
        for i in range(numCourses):
            if inDegree[i] == 0:
                queue.append(i)
        
        while queue:
            course = queue.pop()    
            for postCourse in graph[course]:
                inDegree[postCourse] -= 1
                if not inDegree[postCourse]:
                    queue.append(postCourse)
        
        for idx in range(numCourses):
            if inDegree[idx] > 0:
                return False
        
        return True

 

 

"It can not finish all courses" means that there is cycle in given course schedule. Therefore, I just need to check if there is cycle or not. There may be many solutions of finding out cycle in graph, I thought of 2 solutions using DFS and Topology sort.