There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course ai first if you want to take course bi.
[0, 1] indicates that you have to take course 0 before you can take course 1.Prerequisites can also be indirect. 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.
You are also given an array queries where queries[j] = [uj, vj]. For the jth query, you should answer whether course uj is a prerequisite of course vj or not.
Return a boolean array answer, where answer[j] is the answer to the jth query.
Example 1:
Input: numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]] Output: [false,true] Explanation: The pair [1, 0] indicates that you have to take course 1 before you can take course 0. Course 0 is not a prerequisite of course 1, but the opposite is true.
Example 2:
Input: numCourses = 2, prerequisites = [], queries = [[1,0],[0,1]] Output: [false,false] Explanation: There are no prerequisites, and each course is independent.
Example 3:
Input: numCourses = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]] Output: [true,true]
Constraints:
2 <= numCourses <= 1000 <= prerequisites.length <= (numCourses * (numCourses - 1) / 2)prerequisites[i].length == 20 <= ai, bi <= numCourses - 1ai != bi[ai, bi] are unique.1 <= queries.length <= 1040 <= ui, vi <= numCourses - 1ui != viThe Union-Find algorithm (also known as Disjoint Set Union, or DSU) can be used to efficiently determine the connected components of a graph. Using path compression and union by rank, it supports finding the connected component representatives in near constant time. By representing the courses as nodes and prerequisites as directed edges, we can enable union operations for direct prerequisite relationships.
This Python implementation uses a Union-Find data structure to manage and find the connected components. For each query, if the connected components of the courses match, then it means course u is an indirect prerequisite of course v. The union and find operations are modified by path compression to ensure efficiency.
Java
Time Complexity: O(n + m) for n queries and m union operations, assuming almost constant time for find and union operations due to path compression.
Space Complexity: O(n) space complexity to store the union-find data structures.
The Floyd-Warshall algorithm is a classic algorithm for finding shortest paths in a directed graph with non-negative weights. In this context, it can be used to compute the transitive closure of the graph, meaning for every pair (i, j), we determine if there's a path from i to j. This matches our problem definition when deciding if one course is a prerequisite for another.
This Python solution applies the Floyd-Warshall algorithm to compute the reachability matrix of courses. By iterating through all triples of courses, we fill out the reach matrix to answer every query in constant time. This determines if a path (prerequisite chain) exists between any two courses.
Java
Time Complexity: O(n^3) due to the three nested loops for each pair of courses.
Space Complexity: O(n^2) for the reachability matrix.
| Approach | Complexity |
|---|---|
| Union-Find with Path Compression | Time Complexity: O(n + m) for n queries and m union operations, assuming almost constant time for find and union operations due to path compression. |
| Floyd-Warshall Algorithm | Time Complexity: O(n^3) due to the three nested loops for each pair of courses. |
Course Schedule IV - Leetcode 1462 - Python • NeetCodeIO • 11,768 views views
Watch 9 more video solutions →Practice Course Schedule IV with our built-in code editor and test cases.
Practice on FleetCode