deftopoSort(G): in_degree = {node:0for node in G} for u in G: for v in G[u]: in_degree[v] += 1
queue = [u for u in in_degree if in_degree[u] == 0] res = [] while queue: s = queue.pop() res.append(s) for u in G[s]: in_degree[u] -= 1 if in_degree[u] == 0: queue.append(u) return res
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.
classSolution: defcanFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool: G = {node:[] for node inrange(numCourses)} for edge in prerequisites: G[edge[1]].append(edge[0]) deftop_sort(G): in_degree = {node: 0for node in G} for u in G: for v in G[u]: in_degree[v] += 1 queue = [node for node in in_degree if in_degree[node] == 0] res = [] while queue: cur_node = queue.pop() res.append(cur_node) for v in G[cur_node]: in_degree[v] -= 1 if in_degree[v] == 0: queue.append(v) returnTrueiflen(res) == len(G) elseFalse return top_sort(G)