Problem description

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?

Example 1:

Input: 2, [[1,0]] Output: true Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible. Example 2:

Input: 2, [[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. Note:

The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented. You may assume that there are no duplicate edges in the input prerequisites.

Solution

1. The problem is to check whether the courses form a directed acyclic graph (DAG). We can use either DFS or BFS to try to do topological sorting of the courses.
2. For DFS
   1. We color the node as White initially, then as we start visiting the node, we color it as Grey.
   2. For each of its neighbor, if the color is White, we recursively visit it. If the recursive result is False, we stop and return False. Otherwise, we continue.
   3. If the color is Grey, then we have a cycle, we return False
   4. If the color is Black, then we have finished visiting this neighbor node (and its descendants)
   5. Now we finished visiting all neighbor nodes, we color current node as Black

Below is my python implementation

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        color = ['White' for i in range(numCourses)]
        edgemap = collections.defaultdict(list)
        for prerequisite in prerequisites:
            x, y = prerequisite
            edgemap[x].append(y)
        
        def dfs(i:int, edgemap:dict)->bool:
            color[i] = 'Grey'
            for j in edgemap[i]:
                if color[j] == 'White':
                    if dfs(j, edgemap) == False:
                        return False
                elif color[j] == 'Black':
                    continue
                else:
                    return False
            color[i] = 'Black'
            return True
        
        for i in range(numCourses):
            if color[i] == 'White':
                if not dfs(i, edgemap):
                    return False
        return True
				

1. For BFS
   1. For each course node, we keep record of its in degree (how many courses depend on this course).
   2. We iterate through the courses and find the course not visited before and with in degree equals 0. If we can’t find, means there are cycles in the graph. We return False
   3. Otherwise, we set the course visited be True and for each neighbors of the node, we decrement their in degree by 1.
   4. We loop until all the in degrees are zero. (That is any of the in degree is not zero).
   5. Finally, if we reached the state with all in degrees equal 0, we return True

Below is my python implementation

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        indegrees = [0 for i in range(numCourses)]
        edgemap = collections.defaultdict(set)
        visited = [False for i in range(numCourses)]
        for prerequisite in prerequisites:
            x, y = prerequisite
            indegrees[y] += 1
            edgemap[x].add(y)        
    
        print(indegrees)
        while any(indegrees):
            idx = -1
            for i in range(numCourses):
                if indegrees[i] == 0 and visited[i] == False:
                    visited[i] = True
                    idx = i
                    break
            else:
                return False
            for node in edgemap[idx]:
                indegrees[node] -= 1    
        return True