【Java|golang】210. 课程表 II---拓扑排序
一、拓扑排序的定义：
先引用一段百度百科上对于拓扑排序的定义：
对一个有向无环图 ( Directed Acyclic Graph 简称 DAG ) G 进行拓扑排序，是将 G
中所有顶点排成一个线性序列，使得图中任意一对顶点 u 和 v ，若边 < u , v > ∈ E ( G )，则 u 在线性序列中出现在 v之前。通常，这样的线性序列称为满足拓扑次序 ( Topological Order )
的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
总结起来有三个要点：
1.有向无环图；
2.序列里的每一个点只能出现一次；
3.任何一对 u 和 v ，u 总在 v 之前（这里的两个字母分别表示的是一条线段的两个端点，u 表示起点，v 表示终点）；
二、样例：
现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。
例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。
返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。
示例 1：
输入：numCourses = 2, prerequisites = [[1,0]]
输出：[0,1]
解释：总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。
示例 2：
输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出：[0,2,1,3]
解释：总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。
示例 3：
输入：numCourses = 1, prerequisites = []
输出：[0]
提示：
1 <= numCourses <= 2000
0 <= prerequisites.length <= numCourses * (numCourses - 1)
prerequisites[i].length == 2
0 <= ai, bi < numCourses
ai != bi
所有[ai, bi] 互不相同
public int[] findOrder(int numCourses, int[][] prerequisites) {int[] inDegree=new int[numCourses];Map<Integer, List<Integer>> directMap = new HashMap<>();for (int[] prerequisite : prerequisites) {List<Integer> list = directMap.getOrDefault(prerequisite[1], new ArrayList<>());list.add(prerequisite[0]);directMap.put(prerequisite[1],list);inDegree[prerequisite[0]]++;}Queue<Integer> queue=new LinkedList<>();for (int i = 0; i < numCourses; i++) {if (inDegree[i] == 0) {queue.add(i);}}int index=0;int[] res = new int[numCourses];while (!queue.isEmpty()){Integer poll = queue.poll();res[index++]=poll;List<Integer> list = directMap.getOrDefault(poll, new ArrayList<>());for (Integer i : list) {inDegree[i]--;if (inDegree[i]==0){queue.add(i);}}}return index==numCourses?res:new int[0];}
func findOrder(numCourses int, prerequisites [][]int) []int {inDegree:=make([]int,numCourses)directMap:=make(map[int][]int,0)for _, v := range prerequisites {directMap[v[1]] = append(directMap[v[1]], v[0])inDegree[v[0]]++}queue:=make([]int,0)for i := 0; i < numCourses; i++ {if inDegree[i] == 0 {queue=append(queue, i)}}index:=0res := make([]int,numCourses)for len(queue)!=0 {poll := queue[0]queue=queue[1:]res[index]=pollindex++for _,i := range directMap[poll] {inDegree[i]--if inDegree[i]==0{queue=append(queue, i)}}}if index!=numCourses{return []int{}}return res
}
