aboutsummaryrefslogtreecommitdiff
path: root/course_schedule4.py
blob: 9f9b21d05b47023b119b6bef9d169cbc8d9f2c86 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
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]],
        )
    )