脚本宝典收集整理的这篇文章主要介绍了图算法(三)-拓扑排序,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
There are a total of numCourses
courses you have to take, labeled from 0
to numCourses - 1
. You are given an array prerequisites
where prerequisites[i] = [ai, bi]
indicates that you must take course bi
first if you want to take course ai
.
[0, 1]
, indicates that to take course 0
you have to first take course 1
.Return true
if you can finish all courses. Otherwise, return false
.
Example 1:
Input: numCourses = 2, prerequisites = [[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: numCourses = 2, prerequisites = [[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.
Constraints:
1 <= numCourses <= 105
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
bfs
class Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { //1.build graph //2.build dgree Map<Integer,List<Integer>> map = new HashMap(); int[] degree = new int[numCourses]; for(int[] pair:prerequisites){ List<Integer> list = map.getOrDefault(pair[1],new ArrayList()); list.add(pair[0]); map.put(pair[1],list); degree[pair[0]]++; } //3.find the entry(degree==0) Queue<Integer> queue = new LinkedList(); for(int i=0;i<numCourses;i++) if(degree[i]==0) queue.offer(i); //4.toplogical int count=0; while(!queue.isEmpty()){ int curr = queue.poll(); count++; for(int other:map.getOrDefault(curr,Arrays.asList())){ if(--degree[other] == 0) queue.offer(other);//入度为0的时候进queue } } return count==numCourses; } }
dfs
以上是脚本宝典为你收集整理的图算法(三)-拓扑排序全部内容,希望文章能够帮你解决图算法(三)-拓扑排序所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。