210. Course Schedule II

210. Course Schedule II

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.

For example:

2, [[1,0]]

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]

4, [[1,0],[2,0],[3,1],[3,2]]

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.

思路： Topo-sort 在leetcode里只有几个题目，而且逻辑完全一样。只要清楚的记得几大步骤就可以解题啦。

建立入度indegree.组成cousePairs，把原来输入的无规律edges，转换成 out -> List 另一种表示图的方法。找到indegree为零的点，放到Queue里，也就是我们topo-sort 图的入口。从Q里弹出点，写到结果里。对于它的neighbors, 也就是out指向的in。这里题目意思是preCourses, 因为我们已经上过这门课，所以需要上的课也就少了一门。如果这些neighbors的入度也变成0，也就变成了新的入口，加入到Q里，重复4.返回结果。

class Solution { public int[] findOrder(int numCourses, int[][] prerequisites) { int[] res = new int[numCourses]; int[] indegree = new int[numCourses]; List[] pairs = new List[numCourses]; for(int[] pre : prerequisites){ int in = pre[0], out = pre[1]; indegree[in]++; if(pairs[out] == null) pairs[out] = new ArrayList(); pairs[out].add(in); } Queue q = new LinkedList<>(); for(int i = 0; i < numCourses; i++){ if(indegree[i] == 0) q.offer(i); } int t = 0; while(!q.isEmpty()){ int out = q.poll(); res[t++] = out; if(pairs[out] == null) continue; for(int in : pairs[out]){ indegree[in]--; if(indegree[in] == 0) q.offer(in); } } return t == numCourses ? res : new int[0]; }}

/** * @param {number} numCourses * @param {number[][]} prerequisites * @return {number[]} */var findOrder = function(numCourses, prerequisites) { let graph = buildGraph(numCourses, prerequisites) let visited = new Set let order = [] let cycle = false for (let node of Object.keys(graph)) { if (visited.has(node)) continue dfs(node) } return cycle ? [] : order function dfs(start, visiting = new Set) { if (visiting.has(start)) { cycle = true return } visiting.add(start) for (let neighbor of graph[start]) { if (!visited.has(neighbor)) dfs(neighbor, visiting) } visited.add(start) order.push(+start) } };function buildGraph(num, prereqs) { let graph = {} for (let [a, b] of prereqs) { if (graph[a]) { graph[a].push(String(b)) } else { graph[a] = [String(b)] } if (!graph[b]) { graph[b] = [] } } for (let i = 0; i < num; i++) { if (!graph[i]) { graph[i] = [] } } return graph}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。