1462. 课程表 IV (opens new window)

有向图的根可达性算法

根据题意，题目要求判断两个节点是否是先决关系，本质上是判断有向图的根可达性问题。

两个节点的可达性采用以下几种数据结构：

• 使用二维数组来维护两个节点的可达性关系，floyed[i] [j]=true表示 i 节点作为 j节点的前驱
• 使用Map<Integer, Set<Integer>>集合映射保存节点的前驱结果，key为前驱节点，Set为所有后置节点的集合

本题目采用二维数组来结构化数据，而不使用集合映射的原因在于，Map既是更新对象又是被遍历对象，需要开辟新的空间保存已访问节点，不能随机访问两个节点之间的可达性，需要遍历Set。

1.floyed

简单粗暴三层for遍历所有节点，第一层枚举所有中间节点，第二层枚举起始节点，第三层枚举所有终点节点。floyed算法的精髓就是最外层控制中间节点。

算法的关键在于最外层枚举中间节点。这是从动态规划推导而来，对于第k个中间节点，任意两个节点的最短距离只有两种情况，要么通过第k个节点，要么不通过第k个节点(保留前k-1个节点的计算结果)。

class Solution {
    public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
        boolean[][] floyed = new boolean[numCourses][numCourses];
        for (int[] prerequisite : prerequisites) {
            floyed[prerequisite[0]][prerequisite[1]] = true;
        }
        for (int i = 0; i < numCourses; i++) {
            for (int j = 0; j < numCourses; j++) {
                for (int k = 0; k < numCourses; k++) {
                    if(floyed[j][i]&&floyed[i][k]) floyed[j][k]=true;
                }
            }
        }
        
        List<Boolean> res=new ArrayList<>();
        for(int i=0;i<queries.length;i++){
            if(floyed[queries[i][0]][queries[i][1]]) res.add(true);
            else res.add(false);
        }
        return res;
    }
}

2.广搜+拓扑排序

Map保存节点之间的前驱后继关系，val保存每个节点的入度。

• 将入度为0的节点加入队列queue
• 遍历队列，每次出队一个元素pre，进行如下操作：
  • 找到pre的所有直接后继节点集合
  • 建立pre与所有直接后继节点的先决关系，入度减一
  • 遍历所有节点，刷新建立新的连通性，这里是刷新到达所有节点到达上述pre后继集合的联通性。(注意这里是更新时，pre后继节点一定是作为终点)
• 队列加入新的入度为0的节点

class Solution {
    public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
        Map<Integer, Set<Integer>> map = new HashMap<>();
        boolean[][] floyed = new boolean[numCourses][numCourses];
        int[] val=new int[numCourses];
        for(int i=0;i<prerequisites.length;i++){
            if(map.containsKey(prerequisites[i][0])){
                Set<Integer> set=map.get(prerequisites[i][0]);
                set.add(prerequisites[i][1]);
            }
            else{
                Set<Integer> set=new HashSet<>();
                set.add(prerequisites[i][1]);
                map.put(prerequisites[i][0],set);
            }
            val[prerequisites[i][1]]++;
        }
        
        Queue<Integer> queue = new LinkedList<>();
        for(int i=0;i<numCourses;i++){
            if(val[i]==0){
                queue.offer(i);
            }
        }
        while(!queue.isEmpty()){
            Integer pre = queue.poll();
            if (map.containsKey(pre)) {
                for (Integer curr : map.get(pre)) {
                    floyed[pre][curr] = true;
                    for (int i = 0; i < numCourses; i++) {
                        floyed[i][curr] = floyed[i][curr] || floyed[i][pre];
                    }
                    val[curr]--;
                    if(val[curr]==0) queue.offer(curr);
                }
            }
        }
        
        List<Boolean> res=new ArrayList<>();
        for(int i=0;i<queries.length;i++){
            if(floyed[queries[i][0]][queries[i][1]]) res.add(true);
            else res.add(false);
        }
        return res;
    }
}