[Leetcode] Course Schedule

This is a classical graph problem - the key is to detect cycle in a directed graph. This is usually done by flagging a node by 0, 1, 2, where 0 represents never visited, 1 in the stack, 2 visited. If at any time, we visited a node which status is 1, that it is in stack yet we visited it again, then it means that there is a cycle.

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.

Code: 

class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """
        g = [[] for _ in range(numCourses)]
        for a, b in prerequisites:
            g[b].append(a)
            
        visited = [0 for _ in range(numCourses)]
        
        def dfs(node, visited):
            visited[node] = 1
            for v in g[node]:
                if visited[v] == 1:
                    return False
                elif visited[v] == 0:
                    if not dfs(v, visited):
                        return False
            visited[node] = 2
            return True
            
        for i in range(numCourses):
            if visited[i] == 0:
                if not dfs(i, visited):
                    return False
        return True