title: Topological Sort
body: <p>Consider the following algorithm for topological sort given in my textbook:</p>
  
  <pre><code>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"
  </code></pre>
  
  <p>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.</p>
  
  <p>How can I correct this algorithm to properly check for a dicycle?</p>
  
  <p><strong>Edit:</strong></p>
  
  <p>Presently, I'm simply skirting the S problem, by checking the value of i at the end:</p>
  
  <pre><code>if i != n + 1
     return "G has a dicycle"
  </code></pre>