# （1462. 课程表 IV leetcode）广搜+拓扑-------------------Java实现

（1462. 课程表 IV leetcode）广搜+拓扑-------------------Java实现

题目表述

你总共需要上 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 个查询的答案。

样例

条件

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

思路

1、广搜+拓扑，暴力解法，其实可以把数据结构由hashset变成二维数组记录，这样会省时间空间
建议再做一边。

注意点

ac代码

Java方法一:

class Solution {
    public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
        HashSet<Integer> SourceToTarget[] = new HashSet[numCourses];
        HashSet<Integer> BeforeSource[] = new HashSet[numCourses];
        int source[] = new int[numCourses];
        List<Boolean> result = new ArrayList<>();
        for (int i=0;i<numCourses;i++) {
            SourceToTarget[i] = new HashSet<>();
            BeforeSource[i] = new HashSet<>();
        }for (int[] node:prerequisites)
        if (!SourceToTarget[node[0]].contains(node[1])) {
            source[node[1]]++;
            SourceToTarget[node[0]].add(node[1]);
            BeforeSource[node[1]].add(node[0]);
        }
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0;i<numCourses;i++)
            if (source[i]==0)
                q.offer(i);
        while(!q.isEmpty())
        {
            int now = q.poll();
            for (Integer target:SourceToTarget[now])
            {
                source[target]--;
                if (source[target]==0)
                    q.offer(target);
                for (Integer s:BeforeSource[now])
                if (!BeforeSource[target].contains(s))
                    BeforeSource[target].add(s);
            }

        }
        for(int i=0;i<numCourses;i++)
        {
            for (int s:BeforeSource[i])
                System.out.print(s+" ");
            System.out.println();
        }

        //judge
        for (int i=0;i<queries.length;i++)
            if(BeforeSource[queries[i][1]].contains(queries[i][0]))
                result.add(Boolean.TRUE);
            else
                result.add(Boolean.FALSE);
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/squares-of-a-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。