本文最后更新于128 天前,其中的信息可能已经过时,如有错误请发送邮件到3368129372@qq.com
本质上是判断一个有向图有没有闭环(注意指向)
把一个 有向无环图 转成 线性的排序 就叫 拓扑排序
如何判断?
本质上是bfs,先找到入度为0的便利,入度为0说明走的到,这些相邻的节点入度就能直接减一了,再找出剪完后的入度,是否有为零的,有0的可以放入一个队列中方便便利。...如此往复,如果最后全为0则说明没环。
代码示例:
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
int[] ans = new int[numCourses];
Map<Integer, List<Integer>> map = new HashMap<>();
Queue<Integer> q = new ArrayDeque<>();
int alreadyFix = 0;
for(int[] cur : prerequisites) {
ans[cur[0]]++;
List<Integer> list = map.getOrDefault(cur[1], new ArrayList<>());
list.add(cur[0]);
map.put(cur[1], list);
}
for(int i = 0;i<numCourses;i++){
if(ans[i]==0){
q.offer(i);
alreadyFix++;
}
}
while(!q.isEmpty()) {
Integer cur = q.poll();
List<Integer> jiechu = map.getOrDefault(cur, new ArrayList<>());
for(int i : jiechu) {
ans[i]--;
if(ans[i]==0) {
q.offer(i);
alreadyFix++;
}
}
}
return alreadyFix == numCourses;
}
}