前言

想要精通算法和SQL的成长之路 - 系列导航

做这个题目之前可以回顾一下：课程表II

一. 课程表IV （拓扑排序）

原题链接

这道题目在课程表II的基础上做了什么升华呢？也就是课程之间的先决条件是可以继承的。 那么我们在原本的拓扑排序基础上可以做些什么操作？

• 我们需要记录这个先决关系，记录每一对课程之间是否存在直接或间接的先决条件。这里我们可以用一个二维数组matrix来存储。
• 最终的返回结果，根据queries数组的一二维坐标可以直接查询。

我们先看下拓扑排序中的几个重要步骤：

1.构建邻接图以及计算每个节点的入度数。

List[] adj = new List[numCourses];
// 初始化集合而已
for (int i = 0; i < numCourses; i++) {adj[i] = new ArrayList<Integer>();
}
int[] inDegree = new int[numCourses];
for (int[] prerequisite : prerequisites) {// [0,1] --> 0->1adj[prerequisite[0]].add(prerequisite[1]);// 后继节点的入度+1inDegree[prerequisite[1]]++;
}

2.利用queue队列，将入度为0的先入队，并做后续的递归操作。入度为0，则说明没有先决课程，可以直接学习。

LinkedList<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {if (inDegree[i] == 0) {queue.offer(i);}
}

3.开始递归：

while (!queue.isEmpty()) {Integer pre = queue.poll();List<Integer> nextNode = adj[pre];for (Integer next : nextNode) {// 入度-1inDegree[next]--;// 入度为0之后，立马加入队列，进入下一次递归if (inDegree[next] == 0) {queue.offer(next);}}
}

那么本题目将在第三个步骤中增添核心逻辑：

1. 我们准备一个二维数组matrix。
2. 同时在递归过程中，将对应的指向关系设置为true，代表他们之间的有向性 pre --> next。如果说存在节点 i --> pre。那么一定有i --> next。

boolean[][] matrix = new boolean[numCourses][numCourses];
while (!queue.isEmpty()) {Integer pre = queue.poll();List<Integer> nextNode = adj[pre];for (Integer next : nextNode) {// 当前的有向性matrix[pre][next] = true;// 同时遍历一次数组，在满足pre->next的前提下，如果有i->pre。必定有i->next (i->pre->next)// 注意，这里的遍历，我们的纵坐标是固定的，因为纵坐标是指向地（后继节点），而出发点我们应该遍历所有的情况for (int i = 0; i < numCourses; i++) {if (matrix[i][pre]) {matrix[i][next] = true;}}inDegree[next]--;if (inDegree[next] == 0) {queue.offer(next);}}
}

最后根据题目的入参queries，像查字典一样，从matrix字典中查出每组的答案：

ArrayList<Boolean> res = new ArrayList<>();
for (int[] query : queries) {res.add(matrix[query[0]][query[1]]);
}
return res;

最终完整代码如下：

public class Test1462 {public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {List[] adj = new List[numCourses];boolean[][] matrix = new boolean[numCourses][numCourses];for (int i = 0; i < numCourses; i++) {adj[i] = new ArrayList<Integer>();}int[] inDegree = new int[numCourses];for (int[] prerequisite : prerequisites) {adj[prerequisite[0]].add(prerequisite[1]);inDegree[prerequisite[1]]++;}LinkedList<Integer> queue = new LinkedList<>();for (int i = 0; i < numCourses; i++) {if (inDegree[i] == 0) {queue.offer(i);}}while (!queue.isEmpty()) {Integer pre = queue.poll();List<Integer> nextNode = adj[pre];for (Integer next : nextNode) {matrix[pre][next] = true;for (int i = 0; i < numCourses; i++) {if (matrix[i][pre]) {matrix[i][next] = true;}}inDegree[next]--;if (inDegree[next] == 0) {queue.offer(next);}}}ArrayList<Boolean> res = new ArrayList<>();for (int[] query : queries) {res.add(matrix[query[0]][query[1]]);}return res;}
}