diff options
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]], + ) + ) |