解题思路:
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
int[] inDegree = new int[numCourses];//存每个结点的入度
List<List<Integer>> res = new ArrayList<>();//存结点之间依赖关系
Queue<Integer> queue = new LinkedList<>();
//初始化二维List集合
for(int i = 0; i < numCourses; i++)
res.add(new ArrayList<>());
//取出每一对结点
for(int[] temp : prerequisites){
inDegree[temp[0]]++;
res.get(temp[1]).add(temp[0]);
}
//先把所有入度为0的结点加入队列
for(int i = 0; i < numCourses; i++)
if(inDegree[i] == 0)
queue.add(i);
while(!queue.isEmpty()){
int pre = queue.poll();
numCourses--;
//根据依赖关系,把入度-1
for(int cur : res.get(pre)){
if(--inDegree[cur] == 0)
queue.add(cur);
}
}
return numCourses == 0;
}
}