网站代理服务器有问题,学做网站书籍,it培训学校it培训机构,电视直播网站建设题目#xff1a;
你这个学期必须选修 numCourses 门课程#xff0c;记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出#xff0c;其中 prerequisites[i] [ai, bi] #xff0c;表示如果要学习课程 ai 则 必须 先学习…题目
你这个学期必须选修 numCourses 门课程记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出其中 prerequisites[i] [ai, bi] 表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如先修课程对 [0, 1] 表示想要学习课程 0 你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习如果可以返回 true 否则返回 false 。 class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {int[] indegrees new int[numCourses]; // 入度表ListListInteger adjacency new ArrayList();QueueInteger queue new LinkedList();for (int i 0; i numCourses; i) adjacency.add(new ArrayList()); // 初始化 0到n-1门课,每门课对应一个List,用于该课是谁的先修课for (int[] cp : prerequisites) {indegrees[cp[0]];adjacency.get(cp[1]).add(cp[0]); // 该课是谁的先修课}// 将所有入度为 0 的节点入队for (int i 0; i numCourses; i) {if (indegrees[i] 0)queue.add(i);}// bfswhile (!queue.isEmpty()) {int pre queue.poll();numCourses--;for (int cur : adjacency.get(pre))if (--indegrees[cur] 0) queue.add(cur);}return numCourses 0;}
} class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {ListListInteger adjacency new ArrayList();for (int i 0; i numCourses; i) adjacency.add(new ArrayList()); // 初始化 0到n-1门课,每门课对应一个List,用于该课是谁的先修课int[] flags new int[numCourses]; // 标志数组for (int[] cp : prerequisites) {adjacency.get(cp[1]).add(cp[0]); // 该课是谁的先修课}for (int i 0; i numCourses; i) {if (!dfs(adjacency, flags, i))return false;}return true;}// 存在环返回false, 不存在返回trueprivate boolean dfs(ListListInteger adjacency, int[] flags, int i) {if(flags[i] 1) return false;if(flags[i] -1) return true;flags[i] 1;for(Integer j : adjacency.get(i)) {if(!dfs(adjacency, flags, j)) return false;}flags[i] -1;return true;}
}
