LeetCode_拓扑排序_BFS_中等_1462.课程表 IV

我就是我 2023-10-15 21:12 117阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

你总共需要上 numCourses 门课，课程编号依次为 0 到 numCourses - 1 。你会得到一个数组 prerequisite ，其中 prerequisites\[i\] = \[ai, bi\] 表示如果你想选 bi 课程，你必须先选 ai 课程。

有的课会有直接的先修课程，比如如果想上课程 1 ，你必须先上课程 0 ，那么会以 \[0,1\] 数对的形式给出先修课程数对。先决条件也可以是间接的。如果课程 a 是课程 b 的先决条件，课程 b 是课程 c 的先决条件，那么课程 a 就是课程 c 的先决条件。

你也得到一个数组 queries ，其中 queries\[j\] = \[uj, vj\]。对于第 j 个查询，您应该回答课程 uj 是否是课程 vj 的先决条件。返回一个布尔数组 answer，其中 answer\[j\] 是第 j 个查询的答案。

**示例 1：**  
![在这里插入图片描述][431b886e441548a6944c9be1e991634a.png]  
输入：numCourses = 2, prerequisites = \[\[1,0\]\], queries = \[\[0,1\],\[1,0\]\]  
输出：\[false,true\]  
解释：课程 0 不是课程 1 的先修课程，但课程 1 是课程 0 的先修课程。

**示例 2：**  
输入：numCourses = 2, prerequisites = \[\], queries = \[\[1,0\],\[0,1\]\]  
输出：\[false,false\]  
解释：没有先修课程对，所以每门课程之间是独立的。

**示例 3：**  
![在这里插入图片描述][8929f0ef69a0422b8ac8acb1bd9b4dd5.png]  
输入：numCourses = 3, prerequisites = \[\[1,2\],\[1,0\],\[2,0\]\], queries = \[\[1,0\],\[1,2\]\]  
输出：\[true,true\]

**提示：**  
2 <= numCourses <= 100  
0 <= prerequisites.length <= (numCourses \* (numCourses - 1) / 2)  
prerequisites\[i\].length == 2  
0 <= ai, bi <= n - 1  
ai != bi  
每一对 \[ai, bi\] 都 不同  
先修课程图中没有环。  
1 <= queries.length <= 104  
0 <= ui, vi <= n - 1  
ui != vi

## 2.思路 ##

（1）拓扑排序 & BFS  
本题与 [210.课程表 II][210._ II] 这题类似，可以使用拓扑排序 + BFS 来解决，只不过在遍历图的过程中，需要记录每对节点之间的关系即可，具体代码如下所示。

相关题目：  
[LeetCode\_环检测\_DFS\_中等\_207.课程表][LeetCode_DFS_207.]  
[LeetCode\_拓扑排序\_BFS\_中等\_210.课程表 II][210._ II]  
[LeetCode\_贪心算法\_困难\_630.课程表 III][LeetCode_630._ III]

## 3.代码实现（Java） ##

//思路1————拓扑排序 & BFS
    class Solution {
        
        public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
        
            //邻接表
            List<Integer>[] graph = new ArrayList[numCourses];
            for (int i = 0; i < numCourses; i++) {
        
                graph[i] = new ArrayList<>();
            }
            //保存每个节点的入度
            int[] inDegree = new int[numCourses];
            for (int[] edge : prerequisites) {
        
                graph[edge[0]].add(edge[1]);
                inDegree[edge[1]]++;
            }
            Queue<Integer> queue = new ArrayDeque<>();
            for (int i = 0; i < numCourses; i++) {
        
                if (inDegree[i] == 0) {
        
                    queue.offer(i);
                }
            }
            // isPre[i][j] = true 表示课程 i 是课程 j 的先决条件
            boolean[][] isPre = new boolean[numCourses][numCourses];
            while (!queue.isEmpty()) {
        
                int node = queue.poll();
                for (int next : graph[node]) {
        
                    isPre[node][next] = true;
                    for (int i = 0; i < numCourses; i++) {
        
                        isPre[i][next] = isPre[i][next] || isPre[i][node];
                    }
                    inDegree[next]--;
                    if (inDegree[next] == 0) {
        
                        queue.offer(next);
                    }
                }
            }
            List<Boolean> res = new ArrayList<>();
            for (int[] query : queries) {
        
                res.add(isPre[query[0]][query[1]]);
            }
            return res;
        }
    }

[431b886e441548a6944c9be1e991634a.png]: https://img-blog.csdnimg.cn/431b886e441548a6944c9be1e991634a.png
[8929f0ef69a0422b8ac8acb1bd9b4dd5.png]: https://img-blog.csdnimg.cn/8929f0ef69a0422b8ac8acb1bd9b4dd5.png
[210._ II]: https://xgqngu.blog.csdn.net/article/details/124532046
[LeetCode_DFS_207.]: https://xgqngu.blog.csdn.net/article/details/124522936
[LeetCode_630._ III]: https://blog.csdn.net/weixin_43004044/article/details/132800584