Skills101
← All practice quizzes

Quiz: Topological Sort

5 questions · new set on every retakeNo time limitPass: 60%+10 XP on first pass

Order tasks so that every prerequisite comes first. Kahn's algorithm with in-degrees, the DFS finishing-order method, how both detect a cycle, and the course schedule problem in Python and Java.

Log in to take the quiz

Free account · see your score, answers and explanations, earn XP

  1. Question 1

    A topological order of a directed graph exists if and only if the graph:

  2. Question 2

    In Kahn's algorithm, which nodes go into the queue at the start?

  3. Question 3

    What does this print?

    from collections import deque
    edges = [(0, 1), (0, 2), (1, 3), (2, 3)]
    indeg = [0] * 4
    adj = [[] for _ in range(4)]
    for u, v in edges:
        adj[u].append(v)
        indeg[v] += 1
    q = deque(i for i in range(4) if indeg[i] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    print(order)
    
  4. Question 4

    Kahn's algorithm finishes with 4 nodes in the order, but the graph has 6 nodes. What does this mean?

  5. Question 5

    In the course problem, the pair [a, b] means "to take course a, first take course b". Which edge do you add?

🎯 Today’s placement challenge — 10 questions, no login. Can you score 10/10?Take today’s challenge →