LeetCode知识点总结 - 210

LeetCode 210. Course Schedule II

题目

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

思路

1 Form adjacency list graph from P & compute indegree for each node
2 For the 1st level of BFS iteration, fill up the queue with courses with no prerequisites
3 At each iteration, pop & add the course from queue to ordering ans
4 Decrement indegree of each course for which current course was prerequisite. If the indegree for those courses becomes 0, we can take it next by adding it to queue
5 Continue the process till queue isn’t empty
6 return ans

答案

class Solution:
    def findOrder(self, N, P):
        G, indegree, q, ans = defaultdict(list), [0]*N, deque(), []
        for nxt, pre in P:
            G[pre].append(nxt)
            indegree[nxt] += 1
        
        for i in range(N):
            if indegree[i] == 0:
                q.append(i)
        while q:
            cur = q.popleft()
            ans.append(cur)
            for nextCourse in G[cur]:
                indegree[nextCourse] -= 1
                if indegree[nextCourse] == 0: 
                    q.append(nextCourse)
                    
        return ans if len(ans) == N else []
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19