Topological Sort

Question

Consider the following algorithm for topological sort given in my textbook:

Input: A digraph G with n vertices
Output: A topological ordering v1,v2...vn of G, or the non-existence thereof.

S is an empty stack

for each vertex u in G do
   incount(u) = indeg(u)
   if incount(u) == 0 then
      S.push(u)
i = 1
while S is non-empty do
   u = S.pop()
   set u as the i-th vertex vi
   i ++
   for each vertex w forming the directed edge (u,w) do
      incount(w) --
      if incount(w) == 0 then
         S.push(w)
if S is empty then
   return "G has a dicycle"

I tried implementing the algorithm word-for-word but found that it always complained of a dicycle, whether the graph was acyclic or not. Then, I discovered that the last 2 lines don't fit in correctly. The while loop immediately prior to it exits when S is empty. So, each time, it is assured that the if condition will hold true.

How can I correct this algorithm to properly check for a dicycle?

Edit:

Presently, I'm simply skirting the S problem, by checking the value of i at the end:

if i != n + 1
   return "G has a dicycle"

Answer 1

Your fix is correct. If you didn't push all the nodes in the graph onto S, the graph contains at least one strongly connected component. In other words, you have a cycle.