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, 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.

Example 1:

1
2
3
4
Input: 2, [[1,0]] 
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished   
             course 0. So the correct course order is [0,1] .

Example 2:

1
2
3
4
5
Input: 4, [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] or [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both     
             courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. 
             So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3] .

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 Topological sort:

follow up question for %. Use a vector to store the element that we pop out from the queue. If eventually the size of result vector is equal to numCourses, then there’s no cycle in the graph.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
 def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
 sortedorder = []
 if numCourses <= 0:
 return False
 inDegree = {i : 0 for i in range(numCourses)}
 graph = {i : [] for i in range(numCourses)}
 
 for child, parent in prerequisites:
 graph[parent].append(child)
 inDegree[child] += 1

 sources = deque()
 
 for key in inDegree:
 if inDegree[key] == 0:
 sources.append(key)
 #visited = 0 
 while sources:
 vertex = sources.popleft()
 #visited += 1
 sortedorder.append(vertex)
 for child in graph[vertex]:
 inDegree[child] -= 1
 if inDegree[child] == 0:
 sources.append(child)
 
 if len(sortedorder) != numCourses:
 return []
 return sortedorder
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
 vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
 vector<int> res;
 vector<vector<int> > graph(numCourses, vector<int>(0));
 vector<int> in(numCourses, 0);
 for (auto &a : prerequisites) {
 graph[a.second].push_back(a.first);
 ++in[a.first];
 }
 queue<int> q;
 for (int i = 0; i < numCourses; ++i) {
 if (in[i] == 0) q.push(i);
 }
 while (!q.empty()) {
 int t = q.front();
 res.push_back(t);
 q.pop();
 for (auto &a : graph[t]) {
 --in[a];
 if (in[a] == 0) q.push(a);
 }
 }
 if (res.size() != numCourses) res.clear();
 return res;
 }
};

Solution DFS:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
 def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
 # build indegree map, use result array to keep all visited nodes
 # visit status: -1 visiting, 0 not visit, 1 visited
 # if there's cycle(need to visit visiting node), then return []
 res = []
 graph = [[] for _ in range(numCourses)]
 visited = [0 for i in range(numCourses)]
 
 for pre in prerequisites:
 graph[pre[1]].append(pre[0])
 
 for i in range(numCourses):
 if not self.dfs(graph, visited, i, res):
 return []
 return res[::-1]
 def dfs(self, graph, visited, i, res):
 if visited[i] == 1:
 return True
 if visited[i] == -1:
 return False
 visited[i] = -1
 for nextCourse in graph[i]:
 if not self.dfs(graph, visited, nextCourse, res):
 return False
 visited[i] = 1
 res.append(i)
 return True

time complexity: $O(VE)$
space complexity: $O(V+E)$
reference: