Medium

Course Schedule IV

LAB

For each query [a,b], return true if course a is a prerequisite of course b.

EXAMPLES

Example 1

Input
{
  "numCourses": 2,
  "prerequisites": [
    [
      1,
      0
    ]
  ],
  "queries": [
    [
      0,
      1
    ],
    [
      1,
      0
    ]
  ]
}

Output
[
  false,
  true
]

FUNCTION SHAPE

numCourses: intprerequisites: intMatrixqueries: intMatrix→boolArray

SOLUTION NOTE

This is the same but we need to maintain a list of sets pre_reqs, that contains all pre-req nodes. This is pretty easily updated by the relation: pre_reqs[nbr] |= pre_reqs[curr] | set([curr])

Reveal reference solution +

pythonREFERENCE

def checkIfPrerequisite(self, n: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
    pre_reqs = [set() for _ in range(n)]

    indegree = defaultdict(int)
    adjList = defaultdict(list)
    for u,v in prerequisites:
        indegree[v] += 1
        adjList[u].append(v)

    q = deque([i for i in range(n) if indegree[i] == 0]) # sources

    while q:
        curr = q.popleft()

        for nbr in adjList[curr]:
            pre_reqs[nbr] |= pre_reqs[curr] | set([curr])

            indegree[nbr] -= 1
            if indegree[nbr] == 0: q.append(nbr)

    return [u in pre_reqs[v] for u,v in queries]

TimeO(V^2 + E + Q)

SpaceO(V^2)

Open on LeetCode ↗