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]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].
Topo-sort 在leetcode里只有几个题目,而且逻辑完全一样。只要清楚的记得几大步骤就可以解题啦。1. 建立入度indegree.2. 组成cousePairs,把原来输入的无规律edges,转换成 out -> List 另一种表示图的方法。3. 找到indegree为零的点,放到Queue里,也就是我们topo-sort 图的入口。4. 从Q里弹出点,写到结果里。对于它的neighbors, 也就是out指向的in。这里题目意思是preCourses, 因为我们已经上过这门课,所以需要上的课也就少了一门。如果这些neighbors的入度也变成0,也就变成了新的入口,加入到Q里,重复4.5. 返回结果。
public class Solution { public int[] findOrder(int num, int[][] pres) { int[] res = new int[num]; int[] indegree = new int[num]; List [] pairs = new List[num]; for(int[] pre : pres){ // pre[0] in, pre[1] out 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 < num; 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 == num ? res : new int[0]; }}