LeetCode 1462. 课程表 IV

Categories:

题目描述
思路分析
1. 解法一：传递闭包（推荐）
相似题目

题目描述

✅ 1462. 课程表 IV

思路分析

解法一：传递闭包（推荐）

核心思路：

构建 reach[i][j] 表示 i 是否为 j 的先修课。

使用 Floyd-Warshall 传递闭包：若 reach[i][k] && reach[k][j]，则 reach[i][j] = true。

直接回答每个查询。

复杂度分析：

时间复杂度：O(n^3)。

空间复杂度：O(n^2)。

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Boolean> checkIfPrerequisite(int n, int[][] prerequisites, int[][] queries) {
        boolean[][] reach = new boolean[n][n];
        for (int[] p : prerequisites) {
            reach[p[0]][p[1]] = true;
        }

        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                if (!reach[i][k]) {
                    continue;
                }
                for (int j = 0; j < n; j++) {
                    if (reach[k][j]) {
                        reach[i][j] = true;
                    }
                }
            }
        }

        List<Boolean> res = new ArrayList<>(queries.length);
        for (int[] q : queries) {
            res.add(reach[q[0]][q[1]]);
        }
        return res;
    }
}

func checkIfPrerequisite(n int, prerequisites [][]int, queries [][]int) []bool {
    reach := make([][]bool, n)
    for i := 0; i < n; i++ {
        reach[i] = make([]bool, n)
    }
    for _, p := range prerequisites {
        reach[p[0]][p[1]] = true
    }

    for k := 0; k < n; k++ {
        for i := 0; i < n; i++ {
            if !reach[i][k] {
                continue
            }
            for j := 0; j < n; j++ {
                if reach[k][j] {
                    reach[i][j] = true
                }
            }
        }
    }

    res := make([]bool, len(queries))
    for i, q := range queries {
        res[i] = reach[q[0]][q[1]]
    }
    return res
}

相似题目

题目	难度	考察点
207. 课程表	中等	图遍历
210. 课程表 II	中等	图遍历
1136. 平行课程	中等	拓扑
743. 网络延迟时间	中等	最短路
261. 以图判树	中等	图论

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/62228335