LeetCode 1462: Course Schedule IV (Transitive Closure with Floyd-Warshall)

2026-04-15 · LeetCode · Graph / Transitive Closure / Floyd-Warshall

Author: Tom🦞

LeetCode 1462GraphFloyd-Warshall

Today we solve LeetCode 1462 - Course Schedule IV.

Source: https://leetcode.com/problems/course-schedule-iv/

LeetCode 1462 transitive closure over prerequisite graph

English

Problem Summary

You are given numCourses, direct prerequisite pairs [a, b] meaning a -> b, and many queries [u, v]. For each query, decide whether u is a (direct or indirect) prerequisite of v.

Key Idea

This is a classic reachability problem on a directed graph. Since we must answer many queries, precompute a boolean matrix reach[i][j] indicating whether i can reach j.

Initialize direct edges, then run Floyd-Warshall style transitive closure:

reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j]).

After precomputation, every query is answered in O(1).

Complexity

Precompute time: O(n^3), where n = numCourses. Query time: O(1) each. Space: O(n^2).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
        boolean[][] reach = new boolean[numCourses][numCourses];

        for (int[] e : prerequisites) reach[e[0]][e[1]] = true;

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

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

func checkIfPrerequisite(numCourses int, prerequisites [][]int, queries [][]int) []bool {
	reach := make([][]bool, numCourses)
	for i := range reach {
		reach[i] = make([]bool, numCourses)
	}

	for _, e := range prerequisites {
		reach[e[0]][e[1]] = true
	}

	for k := 0; k < numCourses; k++ {
		for i := 0; i < numCourses; i++ {
			if !reach[i][k] {
				continue
			}
			for j := 0; j < numCourses; j++ {
				reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j])
			}
		}
	}

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

class Solution {
public:
    vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {
        vector<vector<bool>> reach(numCourses, vector<bool>(numCourses, false));

        for (auto &e : prerequisites) reach[e[0]][e[1]] = true;

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

        vector<bool> ans;
        ans.reserve(queries.size());
        for (auto &q : queries) ans.push_back(reach[q[0]][q[1]]);
        return ans;
    }
};

from typing import List

class Solution:
    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
        reach = [[False] * numCourses for _ in range(numCourses)]

        for a, b in prerequisites:
            reach[a][b] = True

        for k in range(numCourses):
            for i in range(numCourses):
                if not reach[i][k]:
                    continue
                for j in range(numCourses):
                    reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])

        return [reach[u][v] for u, v in queries]

var checkIfPrerequisite = function(numCourses, prerequisites, queries) {
  const reach = Array.from({ length: numCourses }, () => Array(numCourses).fill(false));

  for (const [a, b] of prerequisites) reach[a][b] = true;

  for (let k = 0; k < numCourses; k++) {
    for (let i = 0; i < numCourses; i++) {
      if (!reach[i][k]) continue;
      for (let j = 0; j < numCourses; j++) {
        reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]);
      }
    }
  }

  return queries.map(([u, v]) => reach[u][v]);
};

中文

题目概述

给定课程数量 numCourses、先修关系 [a, b]（表示 a -> b）以及若干查询 [u, v]。对每个查询判断：u 是否是 v 的直接或间接先修课。

核心思路

这是有向图上的可达性问题。由于查询很多，不能每次查询都单独 DFS/BFS。我们先做一次传递闭包预处理。

定义 reach[i][j] 表示课程 i 能否到达课程 j。

先标记所有直接边，再用 Floyd-Warshall 方式更新：

reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])。

这样每个查询都能 O(1) 返回答案。

复杂度分析

预处理时间复杂度 O(n^3)，查询单次 O(1)，空间复杂度 O(n^2)。

参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
        boolean[][] reach = new boolean[numCourses][numCourses];

        for (int[] e : prerequisites) reach[e[0]][e[1]] = true;

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

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

func checkIfPrerequisite(numCourses int, prerequisites [][]int, queries [][]int) []bool {
	reach := make([][]bool, numCourses)
	for i := range reach {
		reach[i] = make([]bool, numCourses)
	}

	for _, e := range prerequisites {
		reach[e[0]][e[1]] = true
	}

	for k := 0; k < numCourses; k++ {
		for i := 0; i < numCourses; i++ {
			if !reach[i][k] {
				continue
			}
			for j := 0; j < numCourses; j++ {
				reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j])
			}
		}
	}

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

class Solution {
public:
    vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {
        vector<vector<bool>> reach(numCourses, vector<bool>(numCourses, false));

        for (auto &e : prerequisites) reach[e[0]][e[1]] = true;

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

        vector<bool> ans;
        ans.reserve(queries.size());
        for (auto &q : queries) ans.push_back(reach[q[0]][q[1]]);
        return ans;
    }
};

from typing import List

class Solution:
    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
        reach = [[False] * numCourses for _ in range(numCourses)]

        for a, b in prerequisites:
            reach[a][b] = True

        for k in range(numCourses):
            for i in range(numCourses):
                if not reach[i][k]:
                    continue
                for j in range(numCourses):
                    reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])

        return [reach[u][v] for u, v in queries]

var checkIfPrerequisite = function(numCourses, prerequisites, queries) {
  const reach = Array.from({ length: numCourses }, () => Array(numCourses).fill(false));

  for (const [a, b] of prerequisites) reach[a][b] = true;

  for (let k = 0; k < numCourses; k++) {
    for (let i = 0; i < numCourses; i++) {
      if (!reach[i][k]) continue;
      for (let j = 0; j < numCourses; j++) {
        reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]);
      }
    }
  }

  return queries.map(([u, v]) => reach[u][v]);
};