前言

2023-9-24 15:32:23

以下内容源自《【学习算法】》
仅供学习交流使用

版权

禁止其他平台发布时删除以下此话
本文首次发布于CSDN平台
作者是CSDN@日星月云
博客主页是https://blog.csdn.net/qq_51625007
禁止其他平台发布时删除以上此话

推荐

无

拓扑排序

核心思想

就是先找到入度为0的结点

删除它发出的边

继续找入度为0的结点

直到找不到为止

判断剩下有没有结点

207. 课程表

207. 课程表

解法一

class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {int n=numCourses;HashMap<Integer,ArrayList<Integer>> map=new HashMap<>();for (int i = 0; i < n; i++) {map.putIfAbsent(i,new ArrayList<>());}for(int[] course:prerequisites){map.get(course[0]).add(course[1]);}return topo(map,n);}public boolean topo(HashMap<Integer,ArrayList<Integer>> map,int n){int count=0;Stack<Integer> stack=new Stack<>();for (int i = 0; i < n; i++) {//找到入度为0的点if (map.get(i).size()==0){stack.add(i);}}while (!stack.isEmpty()) {Integer i=stack.pop();for (int j = 0; j < map.size(); j++) {if (map.get(j).contains(i)){map.get(j).remove(i);if (map.get(j).size()==0){stack.add(j);}}}count++;}return count == n;}    
}

解法二

一个入度矩阵 indeg

一个访问变量 visited

class Solution {List<List<Integer>> edges;//有向图int [] indeg;//入度public boolean canFinish(int numCourses, int[][] prerequisites) {edges=new ArrayList<List<Integer>>();for(int i=0;i<numCourses;i++){edges.add(new ArrayList<Integer>());}indeg=new int[numCourses];for(int[] info:prerequisites){edges.get(info[1]).add(info[0]);indeg[info[0]]++;}//拓扑排序Queue<Integer> queue = new LinkedList<Integer>();for(int i=0;i<numCourses;i++){if(indeg[i]==0){queue.offer(i);}}//广度优先搜索int visited=0;while(!queue.isEmpty()){visited++;int u=queue.poll();for(int v:edges.get(u)){indeg[v]--;if(indeg[v]==0){queue.offer(v);}}}return visited==numCourses;}}

最后

2023-9-24 15:45:02

我们都有光明的未来

祝大家考研上岸
祝大家工作顺利
祝大家得偿所愿
祝大家如愿以偿
点赞收藏关注哦