Course Schedule II解答

Question

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, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

Solution

Like Course Schedule problem, we can use DFS or BFS to solve this problem.

DFS

 1 class Solution:
 2     def dfs(self, cur: int, adjacencyList: List[List[int]], visited: List[int], result: List[int]) -> bool:
 3         visited[cur] = 1
 4         neighbors = adjacencyList[cur]
 5         for neighbor in neighbors:
 6             if visited[neighbor] == 1:
 7                 return False
 8             if visited[neighbor] == 0:
 9                 if not self.dfs(neighbor, adjacencyList, visited, result):
10                     return False
11         visited[cur] = 2
12         result.append(cur)
13         return True
14         
15     def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
16         result = []
17         if not prerequisites:
18             for i in range(numCourses):
19                 result.append(i)
20             return result
21         # Build adjacency list
22         adjacencyList = [[] for i in range(numCourses)]
23         for pair in prerequisites:
24             adjacencyList[pair[0]].append(pair[1])
25         # Build visited queue: 0 means unvisited; 1 means start to visit; 2 means complete visit
26         visited = [0] * numCourses
27         for i in range(numCourses):
28             if visited[i] == 0:
29                 dfs_result = self.dfs(i, adjacencyList, visited, result)
30                 if not dfs_result:
31                     return []
32         return result

BFS

 1 class Solution:
 2     def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
 3         result = []
 4         if not prerequisites:
 5             for i in range(numCourses):
 6                 result.append(i)
 7             return result
 8         # Build adjacency list
 9         adjacencyList = [[] for i in range(numCourses)]
10         for pair in prerequisites:
11             adjacencyList[pair[1]].append(pair[0])
12         # Build in-coming edges number list
13         edges = [0] * numCourses
14         for i in range(numCourses):
15             neighbors = adjacencyList[i]
16             for neighbor in neighbors:
17                 edges[neighbor] += 1
18         # Build queue to store in-coming edges = 0
19         zero_incoming = []
20         for i in range(numCourses):
21             if edges[i] == 0:
22                 zero_incoming.append(i)
23         if not zero_incoming:
24             return []
25         # Begin BFS
26         count = 0
27         while zero_incoming:
28             curr = zero_incoming.pop()
29             count += 1
30             result.append(curr)
31             curr_neighbors = adjacencyList[curr]
32             for neighbor in curr_neighbors:
33                 edges[neighbor] -= 1
34                 if edges[neighbor] == 0:
35                     zero_incoming.append(neighbor)
36         if count != numCourses:
37             return []
38         return result