title: Tarjan's strongly connected components algorithm in python not working
body: <p>I implemented the Tarjan's strongly connected components algorithm, according to <a href="http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm#The_algorithm_in_pseudocode" rel="nofollow">wikipedia</a>, in Python, but it isn't working. The algorithm is quite short and I cannot find any difference, so I cannot tell why it isn't working. I tried to check the original paper, but could not find it.</p>
  
  <p>Here is the code.</p>
  
  <pre><code>def strongConnect(v):
    global E, idx, CCs, c, S
    idx[v] = (c, c) #idx[v][0] for v.index # idx[v][1] for v.lowlink
    c += 1
    S.append(v)  
    for w in [u for (v2, u) in E if v == v2]:
      if idx[w][0] &lt; 0:
        strongConnect(w)
        # idx[w] = (idx[w][0], min(idx[v][1], idx[w][1])) #fixed, thx
        idx[v] = (idx[v][0], min(idx[v][1], idx[w][1]))
      elif w in S:
        idx[v] = (idx[v][0], min(idx[v][1], idx[w][0]))
    if (idx[v][0] == idx[v][1]):
      i = S.index(v)
      CCs.append(S[i:])
      S = S[:i]
  
  E = [('A', 'B'), ('B', 'C'), ('C', 'D'), ('D', 'E'), ('E', 'A'), ('A', 'E'), ('C', 'A'), ('C', 'E'), ('D', 'F'), ('F', 'B'), ('E', 'F')]
  idx = {}
  CCs = []
  c = 0
  S = []
  for (u, v) in E:
    idx[u] = (-1, -1)
    idx[v] = (-1, -1)
  for v in idx.keys():
    if idx[v][0] &lt; 0:
      strongConnect(v)
  
  print(CCs)
  </code></pre>
  
  <p>You can <a href="http://desmond.imageshack.us/Himg687/scaled.php?server=687&amp;filename=exampleu.png&amp;res=medium" rel="nofollow">check the graph visually</a> if you prefer. As you can see this is a quite forward translation of the pseudocode in wikipedia. However, this is the output:</p>
  
  <pre><code>[['D', 'E', 'F'], ['B', 'C'], ['A']]
  </code></pre>
  
  <p>There should be only one strongly connected component, not three. I hope the question is right in all its aspects, if not I'm sorry. In any case, thank you very much.</p>