Tarjan's Strongly Connected Component algorithm
1... On line 33 why is node.lowlink = min(node.lowlink, n.index) — shouldn't it be same as line 31: node.lowlink = min(node.lowlink, n.lowlink)?


The code works either way.  The two possibilities are:

I. n.index == node.index, which means the assignment will never change the value of node.lowlink, or

II. n.index &lt; node.index, which means setting node.lowlink to either n.index or n.lowlink will cause node.index to be unequal to node.lowlink, guaranteeing that node will be part of the SCC containing everything on the stack back to the node with an index matching n.lowlink.


  2... Do we have to generate the components on line 40 in the while loop as we pop? Isn't it true that when the algorithm finishes, all the vertices grouped by lowLink should be the SCC?


No, that's not true.  The components of any particular SCC are not guaranteed to have the same .lowlink value, so you can't partition the vertices into SCCs that way.  The .lowlink values are used to determine when to pop the stack; the stack determines what is in an SCC.


  3... Is it ever true that after we recurse in line 30, n may not be in stack?


Yes, n may not be in the stack.  n could be a vertex belonging to a previously identified SCC.  There's a forward link to n obviously but there may be no back link from n or its SCC to the current SCC.