aboutsummaryrefslogtreecommitdiff
path: root/course_schedule4.py
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-01-27 00:14:18 -0700
committerJack Sangdahl <[email protected]>2025-01-27 00:14:18 -0700
commit9d365e2c6d6e30fd3957790282afd1559b18fc0b (patch)
tree34a0cd784876f361497babb92bd2f1e803368628 /course_schedule4.py
parent61a53a0b0943dfdd717eb289139974f21a9ee459 (diff)
downloadleetcode-9d365e2c6d6e30fd3957790282afd1559b18fc0b.tar.gz
leetcode-9d365e2c6d6e30fd3957790282afd1559b18fc0b.zip
1462. course schedule 4
Diffstat (limited to 'course_schedule4.py')
-rw-r--r--course_schedule4.py53
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]],
+ )
+ )