Here is Kahn's algorithm:
function kahnTopoSort(n, adj):
indegree = array of size n, all 0
for u from 0 to n - 1:
for v in adj[u]:
indegree[v] = indegree[v] + 1
q = queue
for u from 0 to n - 1:
if indegree[u] == 0:
q.push(u)
order = empty list
while q is not empty:
u = q.pop()
order.append(u)
for v in adj[u]:
indegree[v] = indegree[v] - 1
if indegree[v] == 0:
q.push(v)
if order.size != n:
return "CYCLE DETECTED"
return order
Time: . Space: .