The topological sorting algorithm (corrected book version) INPUT: a digraph G with n vertices OUTPUT: a topological ordering v_1,v_2,..,v_n of G or an indication that G has a cycle let S be an empty stack FOR each vertex u of G DO incounter(u) <- indeg(u) IF incounter(u) == 0 THEN S.push(u) i <- 1 WHILE S is not empty DO u <- S.pop() number u as the i-th vertex v_i of G i <- i+1 FOR each edge e in G.outIncidentEdges(u) DO w <- G.opposite(u,e) incounter(w) <- incounter(w) - 1 IF incounter(w) == 0; THEN S.push(w) // this final bit differs from the wrong book version: IF i>n THEN RETURN order v_1,v_2,..,v_n ELSE RETURN "G must have a cycle"