Medium

Course Schedule

LAB

Return true if all courses can be completed given prerequisite pairs [course, prerequisite].

EXAMPLES

Example 1

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

Output
true

FUNCTION SHAPE

numCourses: intprerequisites: intMatrix→bool

SOLUTION NOTE

So we construct the directed graph, and indegree array, and initialize the queue as all nodes with indegree 0. We perform bfs. (note that we dont need to iterate for _ in range(len(q)), because we don't necessarily care about the number of levels/layers in the bfs. We can just iterate over each node in the queue) We pop and append the current source node with indegree 0 to the topological order, and consider the neighbours. We decrement indegree and if it becomes a new source, we append to queue. When this bfs is over, if all nodes became sources with indegree 0, this means we have a full, valid topological ordering. This is when len(top_order) == numCourses. (the size of the list is equal to all nodes in the graph)

Reveal reference solution +

pythonREFERENCE

# Kahn's top sort algorithm
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
    adjList = defaultdict(list)
    indegree = [0] * numCourses

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

    q = deque([i for i in range(numCourses) if indegree[i] == 0])

    top_order = []

    while q:
        u = q.popleft()
        top_order.append(u)

        for nbr in adjList[u]:
            indegree[nbr] -= 1
            if indegree[nbr] == 0:
                q.append(nbr)

    return len(top_order) == numCourses

TimeO(V + E)

SpaceO(V + E)

Open on LeetCode ↗