【LeetCode-中等题】210. 课程表 II

题目

这一题是在207题的基础上，要统计拓扑排序的顺序集合，所以只需要在207的基础上加入一个将拓扑排序的节点输出即可（有环无拓扑排序）
【LeetCode-中等题】207. 课程表

方法一：bfs

相比较207题 ，加入一个数组，用于统计拓扑排序节点，
其中拓扑排序的顺序就为队列的出队顺序

//方法一  bfs 广度优先public int[] findOrder(int numCourses, int[][] prerequisites) {int[] cou = new int[numCourses];//课程号入度数组int[] num  = new int[numCourses];//用于存储拓扑排序List<List<Integer>> couList = new ArrayList<>();//课程号指向的课程号集合Queue<Integer> queue = new LinkedList<>();//辅助队列 用于处理入度为0 的课程号for(int i = 0 ;i<numCourses ;i++)//给集合中课程号初始化集合couList.add(new ArrayList<Integer>());for(int[] pre : prerequisites){cou[pre[0]]++;//统计各课程的入度couList.get(pre[1]).add(pre[0]);//给集合中课程号设置指向课程的集合}for(int i = 0 ;i<numCourses ;i++){if(cou[i] == 0) queue.offer(i);//搜索第一个入度为0 的课程号  加入队列}int i = 0;//用于将拓扑排序加入到一个数组用的下标while(!queue.isEmpty()){int ids = queue.poll();numCourses--;//取出一个元素  就让课程号总数-1num[i] = ids;//拓扑排序 取出的元素加入到数组for(int cur : couList.get(ids)){//  couList.get(ids) 根据课程号  取出课程号指向的课程  让被指向的课程号入度 -1if(cou[cur] >= 1 ) cou[cur]--;if(cou[cur] == 0 ) queue.offer(cur);//若当前课程号入度为0  则加入队列}i++;}if(numCourses == 0)  return num;else return new int[0];}

方法二：dfs

相比较207题 ，加入一个数组，用于统计拓扑排序节点，
其中使用一个栈来记录遍历完的节点
拓扑排序的顺序就为栈的出栈顺序

// 方法二  dfs 深度优先int[] cou = null;// 设置全局变量  方便dfs使用int[] num = null;List<List<Integer>> couList = null;boolean valid = true;Deque<Integer> queue = null;public int[] findOrder(int numCourses, int[][] prerequisites) {this.cou = new int[numCourses];//课程号标记数组this.queue = new LinkedList<>();//用于配合输出拓扑排序this.num  = new int[numCourses];//用于存储拓扑排序this.couList = new ArrayList<>();//课程号指向的课程号集合for(int i = 0 ;i<numCourses ;i++)//给集合中课程号初始化集合couList.add(new ArrayList<Integer>());for(int[] pre : prerequisites){couList.get(pre[1]).add(pre[0]);//给集合中课程号设置指向课程的集合}for(int i = 0 ; i<numCourses ;i++){if(cou[i] == 0)  dfs(i);//课程号标记数组对应的值等于 0  开始递归}if(queue.size() != numCourses) return new int[0]; //如果dfs完成之后  栈内元素个数不等于课程号总数  说明 拓扑排序不完整，存在环，自然不能将全部课程学习完，else{//否则就代表无环  可以得到完整的拓扑排序for(int i = 0 ; i<numCourses ; i++){num[i] = queue.pop();//将压栈的课程号取出来 放到数组里面}}  return num;}public void dfs(int i){cou[i] = 1;for(int cur : couList.get(i)){if(cou[cur] == 0){//课程号标记数组对应的值等于 0  继续递归dfs(cur);if(!valid) return ;  //根据标记为判断是否有环  有环说明不能得到拓扑排序 直接返回 不往下面执行了}else if(cou[cur] == 1){//如果搜索中存在环  将标志位设为fasle valid = false;return;}}//一次遍历结束无环  就让该遍历元素位置的课程号数值置为  2  代表以该点进行dfs  无环cou[i] = 2;queue.push(i); //让该dfs完的课程压栈  为什么要压栈  因为最后的拓扑排序，就是栈的出栈顺序}