1.LeetCode207题目链接
https://leetcode-cn.com/problems/course-schedule/
2.题目解析
看完题目之后需要了解下拓扑排序以及图的表示法。该题主要是遍历查询有没有死环。
将入度为 0 的结点放入队列，找到入度为0的子节点并减1，如果能够将子节点入度为0，加入队列重复操作
public boolean canFinish(int numCourses, int[][] prerequisites) {
if (numCourses <= 0) {
return false;
}
int plen = prerequisites.length;
if (plen == 0) {
return true;
}
int[] inDegree = new int[numCourses];
for (int[] p : prerequisites) {
inDegree[p[0]]++;
}
LinkedList<Integer> queue = new LinkedList<>();
// 首先加入入度为 0 的结点
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
queue.addLast(i);
}
}
// 拓扑排序的结果
List<Integer> res = new ArrayList<>();
while (!queue.isEmpty()) {
Integer num = queue.removeFirst();
res.add(num);
// 把邻边全部遍历一下
for (int[] p : prerequisites) {
if (p[1] == num) {
inDegree[p[0]]--;
//是否入度为0
if (inDegree[p[0]] == 0) {
queue.addLast(p[0]);
}
}
}
}
return res.size() == numCourses;
}
image
