企业网站 程序,免费咨询制度,网站建设 环保 图片,免费正能量下载软件课程表
力扣链接#xff1a;207. 课程表
题目描述
你这个学期必须选修 numCourses 门课程#xff0c;记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出#xff0c;其中 prerequisites[i] [ai, bi] #xff0c;表…课程表
力扣链接207. 课程表
题目描述
你这个学期必须选修 numCourses 门课程记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出其中 prerequisites[i] [ai, bi] 表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如先修课程对 [0, 1] 表示想要学习课程 0 你需要先完成课程 1 。 请你判断是否可能完成所有课程的学习如果可以返回 true 否则返回 false 。
示例 思路
拓扑排序问题抓住节点入度和出度的本质特征。 方法一 从入度思考(从前往后排序) 入度为0的节点在拓扑排序中一定排在前面, 然后删除和该节点对应的边, 迭代寻找入度为0的节点。 方法二 从出度思考(从后往前排序) 出度为0的节点在拓扑排序中一定排在后面, 然后删除和该节点对应的边, 迭代寻找出度为0的节点。、
Java代码从入度思考
class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {ListListInteger edgs new ArrayListListInteger();for(int i 0; i numCourses; i) {edgs.add(new ArrayListInteger());}int[] indeg new int[numCourses];for(int[] p : prerequisites) {edgs.get(p[1]).add(p[0]);indeg[p[0]];}QueueInteger queue new LinkedListInteger();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 : edgs.get(u)) {indeg[v]--;if(indeg[v] 0) {queue.offer(v);}}}return visited numCourses;}
}Java代码从出度思考
class Solution {ListListInteger edgs;int[] visited;boolean valid true;public boolean canFinish(int numCourses, int[][] prerequisites) {edgs new ArrayListListInteger();for(int i 0; i numCourses; i) {edgs.add(new ArrayListInteger());}visited new int[numCourses];for(int[] p : prerequisites) {edgs.get(p[1]).add(p[0]);}for(int i 0; i numCourses valid; i) {if(visited[i] 0) {dfs(i);}}return valid;}public void dfs(int u) {visited[u] 1;for(int v : edgs.get(u)) {if(visited[v] 0) {dfs(v);if(!valid) {return;}}else if(visited[v] 1) {valid false;return;}}visited[u] 2;}
}
