Sign in
Skip to solution
hardDSA

What is topological sort and when is it used?

1.2k views
01

Understand the problem

Explain topological ordering.

graphstopological-sort
02

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Nudge consolestandby

Stuck? Beam a request up — the console returns a conceptual nudge that guides your logic without spoiling the implementation.

03

Study the solution

Topological sort linearly orders a DAG so every edge u→v has u before v. Implement via DFS (post-order reversed) or Kahn's algorithm (repeatedly remove zero in-degree nodes). Used for build/task scheduling and dependency resolution; impossible if there's a cycle.

Solution ready — 2 min read

Classified // press E to declassify

04

Read the code

Kahn's algorithm (BFS)
Run Playground
from collections import deque

def topo_sort(n, edges):
    graph = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v in edges:
        graph[u].append(v)
        indeg[v] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in graph[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == n else []   # [] means a cycle


# --- demo ---  edges: 0->1, 0->2, 1->3, 2->3
print(topo_sort(4, [(0, 1), (0, 2), (1, 3), (2, 3)]))   # [0, 1, 2, 3]
05

Join the discussion

Discussion (0)

Sign in to join the discussion.

No responses yet. Be the first to share what you think.

Transmission complete // awaiting log

KEEP THE
STREAK ALIVE.

Dossier 99 of 127 decoded in the Data Structures & Algorithms track. One more won't hurt.

Back to track