diff options
author | Jack Sangdahl <[email protected]> | 2025-01-27 00:14:18 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-01-27 00:14:18 -0700 |
commit | 9d365e2c6d6e30fd3957790282afd1559b18fc0b (patch) | |
tree | 34a0cd784876f361497babb92bd2f1e803368628 /course_schedule4.py | |
parent | 61a53a0b0943dfdd717eb289139974f21a9ee459 (diff) | |
download | leetcode-9d365e2c6d6e30fd3957790282afd1559b18fc0b.tar.gz leetcode-9d365e2c6d6e30fd3957790282afd1559b18fc0b.zip |
1462. course schedule 4
Diffstat (limited to 'course_schedule4.py')
-rw-r--r-- | course_schedule4.py | 53 |
1 files changed, 53 insertions, 0 deletions
diff --git a/course_schedule4.py b/course_schedule4.py new file mode 100644 index 0000000..9f9b21d --- /dev/null +++ b/course_schedule4.py @@ -0,0 +1,53 @@ +# 1462. Course Schedule IV + +""" +there are a total of 'numCourses' courses that you have to take, labeled from +0 to 'numCourses - 1'. you are given an array 'prerequisites' where +'prerequisites[i] = [a_i, b_i]' indicates that you must take course 'a_i' +before 'b_i'. 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] = [u_j, v_j]'. for the j'th query, you should +answer whether course 'u_j' is a prerequisite of course 'v_j' or not. +""" + + +class Solution(object): + def checkIfPrerequisite(self, numCourses, prerequisites, queries): + """ + :type numCourses: int + :type prerequisites: List[List[int]] + :type queries: List[List[int]] + :rtype: List[bool] + """ + connected = [[False] * numCourses for i in range(numCourses)] + for i, j in prerequisites: + connected[i][j] = True + for k in range(numCourses): + for i in range(numCourses): + for j in range(numCourses): + connected[i][j] = connected[i][j] or ( + connected[i][k] and connected[k][j] + ) + return [connected[i][j] for i, j in queries] + + +if __name__ == "__main__": + obj = Solution() + print( + obj.checkIfPrerequisite( + numCourses=2, prerequisites=[[1, 0]], queries=[[0, 1], [1, 0]] + ) + ) + print( + obj.checkIfPrerequisite( + numCourses=2, prerequisites=[], queries=[[1, 0], [0, 1]] + ) + ) + print( + obj.checkIfPrerequisite( + numCourses=3, + prerequisites=[[1, 2], [1, 0], [2, 0]], + queries=[[1, 0], [1, 2]], + ) + ) |