共计 2635 个字符，预计需要花费 7 分钟才能阅读完成。
There are a total of n courses you have to take, labeled from 0 to n-1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
Example 1:
Input: 2, [[1,0]] Output: trueExplanation: 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: 2, [[1,0],[0,1]]Output: falseExplanation: 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.
Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.You may assume that there are no duplicate edges in the input prerequisites.
难道: medium
题目: 课程编号为 0 到 n - 1 的 n 门课程需要我们去学习。学习某些课程需要先学习其预备课程，例如学习课程 0 就要先学习课程 1, 用如下形式表示这种关系 [0, 1]. 给定全部课程数，以及这种课程与课程之前的关系，是否可以完成全部课程学习？
注意：
前置课程是由一些边组成的图不是毗邻的矩阵。
你可以假定前置课程这种关系表示没有重复的输入。
思路：BFS, DFS 拓扑图遍历 1. 找出一个出度为 0 的结点。2. 移除该出度为 0 结点的所有边，然后执行 1.
BFS
Runtime: 6 ms, faster than 91.38% of Java online submissions for Course Schedule.
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
// (Array -> List) to store graph
List<Integer>[] nodes = new ArrayList[numCourses];
for (int i = 0; i < numCourses; i++) {
nodes[i] = new ArrayList<Integer>();
}
// count in degree
int[] inDegree = new int[numCourses];
for (int i = 0; i < prerequisites.length; i++) {
(nodes[prerequisites[i][0]]).add(prerequisites[i][1]);
inDegree[prerequisites[i][1]] += 1;
}
// count zero in degree
int zeroInDegreeCount = 0;
Queue<Integer> zeroInDegreeQueue = new LinkedList<>();
for (int i = 0; i < inDegree.length; i++) {
if (inDegree[i] <= 0) {
zeroInDegreeQueue.add(i);
zeroInDegreeCount++;
}
}
// bfs
while (!zeroInDegreeQueue.isEmpty()) {
for (Integer i : nodes[zeroInDegreeQueue.poll()]) {
if (–inDegree[i] <= 0) {
zeroInDegreeQueue.add(i);
zeroInDegreeCount++;
}
}
}
return zeroInDegreeCount == numCourses;
}
}
DFS
Runtime: 51 ms, faster than 19.25% of Java online submissions for Course Schedule.
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<Integer>[] nodes = new ArrayList[numCourses];
for (int i = 0; i < numCourses; i++) {
nodes[i] = new ArrayList<Integer>();
}
for (int i = 0; i < prerequisites.length; i++) {
(nodes[prerequisites[i][0]]).add(prerequisites[i][1]);
}
boolean[] visited = new boolean[numCourses];
for (int i = 0; i < numCourses; i++) {
boolean hasCircle = dfs(i, visited, nodes);
if (hasCircle) {
return false;
}
}
return true;
}
// function to verify if circle exist
private boolean dfs(int c, boolean[] visited, List<Integer>[] nodes) {
boolean hasCircle = false;
visited = true;
List<Integer> lst = nodes;
for (int i = 0; i < lst.size(); i++) {
if (visited[lst.get(i).intValue()]) {
return true;
}
hasCircle = dfs(lst.get(i), visited, nodes);
}
visited = false;
return hasCircle;
}
}
