开发网站公司交税,物联网技术有哪些,口碑好的做网站,网络公司网站设计一、拓扑排序的定义#xff1a;
先引用一段百度百科上对于拓扑排序的定义#xff1a;
对一个有向无环图 ( Directed Acyclic Graph 简称 DAG ) G 进行拓扑排序#xff0c;是将 G 中所有顶点排成一个线性序列#xff0c;使得图中任意一对顶点 u 和 v #xff0c;若边
先引用一段百度百科上对于拓扑排序的定义
对一个有向无环图 ( 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[] inDegreenew int[numCourses];MapInteger, ListInteger directMap new HashMap();for (int[] prerequisite : prerequisites) {ListInteger list directMap.getOrDefault(prerequisite[1], new ArrayList());list.add(prerequisite[0]);directMap.put(prerequisite[1],list);inDegree[prerequisite[0]];}QueueInteger queuenew LinkedList();for (int i 0; i numCourses; i) {if (inDegree[i] 0) {queue.add(i);}}int index0;int[] res new int[numCourses];while (!queue.isEmpty()){Integer poll queue.poll();res[index]poll;ListInteger list directMap.getOrDefault(poll, new ArrayList());for (Integer i : list) {inDegree[i]--;if (inDegree[i]0){queue.add(i);}}}return indexnumCourses?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 {queueappend(queue, i)}}index:0res : make([]int,numCourses)for len(queue)!0 {poll : queue[0]queuequeue[1:]res[index]pollindexfor _,i : range directMap[poll] {inDegree[i]--if inDegree[i]0{queueappend(queue, i)}}}if index!numCourses{return []int{}}return res
}
