[LeetCode] 1462. Course Schedule IV

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have direct prerequisites, for example, to take course 0 you have first to take course 1, which is expressed as a pair: [1,0]

Given the total number of courses n, a list of direct prerequisite pairs and a list of queries pairs.

You should answer for each queries[i] whether the course queries[i][0] is a prerequisite of the course queries[i][1] or not.

Return a list of boolean, the answers to the given queries.

Please note that if course a is a prerequisite of course b and course b is a prerequisite of course c, then, course a is a prerequisite of course c.

Example 1:

Input: n = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]
Output: [false,true]
Explanation: course 0 is not a prerequisite of course 1 but the opposite is true.

Example 2:

Input: n = 2, prerequisites = [], queries = [[1,0],[0,1]]
Output: [false,false]
Explanation: There are no prerequisites and each course is independent.

Example 3:

Input: n = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]]
Output: [true,true]

Example 4:

Input: n = 3, prerequisites = [[1,0],[2,0]], queries = [[0,1],[2,0]]
Output: [false,true]

Example 5:

Input: n = 5, prerequisites = [[0,1],[1,2],[2,3],[3,4]], queries = [[0,4],[4,0],[1,3],[3,0]]
Output: [true,false,true,false]

Constraints:

2 <= n <= 100
0 <= prerequisite.length <= (n * (n - 1) / 2)
0 <= prerequisite[i][0], prerequisite[i][1] < n
prerequisite[i][0] != prerequisite[i][1]
The prerequisites graph has no cycles.
The prerequisites graph has no repeated edges.
1 <= queries.length <= 10^4
queries[i][0] != queries[i][1]

课程安排IV。题意是一共有 N 门课程需要修，他们的编号是从0到 N - 1。其中有一些课程是有直接的先修课程prerequisites的，会以数对形式表示。现在给你课程总数 N 和一个直接先修课程数对列表 prerequisite 和一个查询对列表 queries。对于每个查询对 queries[i]，请判断 queries[i][0] 是否是 queries[i][1] 的先修课程。

这道题我给出一个比较朴素的解法，还是涉及到拓扑排序。对于这道题，你需要一个入度表 indegree 记录课程的入度和两个hashmap，一个 adj 哈希表用来记录课程之间的邻接关系；一个 preMap 哈希表用来记录课程之间的先修关系。首先对于每一个课程 i ，我们需要为这个课程在邻接表和先修表里创建一个hashset以记录课程之间的关系。

接着遍历直接先修课程数对列表 prerequisite，记录课程的入度，同时也记录各个课程的邻接关系。接着还是跟之前的课程安排的题一样，把入度为0的课程加入queue，意思是从不需要先修课程的课开始找起，去创建课程之间的先修关系。从queue弹出一个课程cur的时候，从邻接哈希表 adj 拿到cur的所有邻接课程，同时因为cur的入度为0所以对于每一个 next 课程而言，cur课程一定是next的先修课程，所以我们在 preMap 里找到 next ，并且把 cur 加入 next 的先修课程里。同时如果 cur 自己也有先修课程，也需要把他们统统加入 next 的先修课程的hashset里。

最后对于需要判断的 queries，因为queries[0]是先修课程，queries[1]是后继课程，所以判断的方式是看看 preMap 里key为queries[0]的hashset是否包含queries[1]。

时间O(n^2)

空间O(n)

Java实现

 1 class Solution {
 2     public List<Boolean> checkIfPrerequisite(int n, int[][] prerequisites, int[][] queries) {
 3         int[] indegree = new int[n];
 4         HashMap<Integer, Set<Integer>> adj = new HashMap<>();
 5         HashMap<Integer, Set<Integer>> preMap = new HashMap<>();
 6         for (int i = 0; i < n; i++) {
 7             preMap.put(i, new HashSet<>());
 8             adj.put(i, new HashSet<>());
 9         }
10         for (int[] pre : prerequisites) {
11             indegree[pre[1]]++;
12             adj.get(pre[0]).add(pre[1]);
13         }
14         Queue<Integer> queue = new LinkedList<>();
15         for (int i = 0; i < n; i++) {
16             if (indegree[i] == 0) {
17                 queue.offer(i);
18             }
19         }
20         while (!queue.isEmpty()) {
21             int cur = queue.poll();
22             Set<Integer> set = adj.get(cur);
23             for (int next : set) {
24                 preMap.get(next).add(cur);
25                 preMap.get(next).addAll(preMap.get(cur));
26                 indegree[next]--;
27                 if (indegree[next] == 0) {
28                     queue.offer(next);
29                 }
30             }
31         }
32         List<Boolean> res = new ArrayList<>();
33         for (int[] pair : queries) {
34             Set<Integer> set = preMap.get(pair[1]);
35             if (set.contains(pair[0])) {
36                 res.add(true);
37             } else {
38                 res.add(false);
39             }
40         }
41         return res;
42     }
43 }