Course schedule#

Levels: level-4

Data structures: graph

Algorithms: dfs, bfs

Description#

There are a total of numCourses courses you have to take, labeled from 0 to numCourses-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?

Constraints:

The input prerequisites is a graph represented by a list of edges, not adjacency matrices.
You may assume that there are no duplicate edges in the input prerequisites.
1 <= numCourses <= 10^5

Examples#

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

1Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
2Output: false
3Explanation: There are a total of 2 courses to take.
4             To take course 1 you should have finished course 0, and to take course 0 you should
5             also have finished course 1. So it is impossible.

Python Solution#

 1class Solution(object):
 2    def canFinish(self, numCourses, prerequisites):
 3        """
 4        :type numCourses: int
 5        :type prerequisites: List[List[int]]
 6        :rtype: bool
 7        """
 8        graph = [[] for _ in range(numCourses)]
 9        visited = [0 for _ in range(numCourses)]
10        # create graph
11        for pair in prerequisites:
12            x, y = pair
13            graph[x].append(y)
14        # visit each node
15        for i in range(numCourses):
16            if not self.dfs(graph, visited, i):
17                return False
18        return True
19
20    def dfs(self, graph, visited, i):
21        # if ith node is marked as being visited, then a cycle is found
22        if visited[i] == -1:
23            return False
24        # if it is done visted, then do not visit again
25        if visited[i] == 1:
26            return True
27        # mark as being visited
28        visited[i] = -1
29        # visit all the neighbours
30        for j in graph[i]:
31            if not self.dfs(graph, visited, j):
32                return False
33        # after visit all the neighbours, mark it as done visited
34        visited[i] = 1
35        return True