Tarjan's algorithm finds the strongly connected components, the maximal sets in which every vertex can reach every other, in one DFS. Vertices are pushed on a stack as they are discovered and stay there while their component is open. The badge is low[u], the earliest open vertex u can reach. When a vertex finishes with low[u] equal to its own discovery time, it is the root of a component and everything above it on the stack is popped as one.
Tarjan's SCC over 7 vertices.
Enter 0 at time 0, push it: stack 0. low[0] starts at 0.
Enter 0, pushed.
Enter 1 at time 1, push it: stack 0 1. low[1] starts at 1.
Enter 1, pushed.
Enter 2 at time 2, push it: stack 0 1 2. low[2] starts at 2.
Enter 2, pushed.
Edge 2 -> 0: 0 is still on the stack, so it is open and in the same component as 2. low[2] drops to disc[0] = 0.
Edge 2 to open vertex 0, low of 2 is 0.
Enter 3 at time 3, push it: stack 0 1 2 3. low[3] starts at 3.
Enter 3, pushed.
Enter 4 at time 4, push it: stack 0 1 2 3 4. low[4] starts at 4.
Enter 4, pushed.
Enter 5 at time 5, push it: stack 0 1 2 3 4 5. low[5] starts at 5.
Enter 5, pushed.
Edge 5 -> 3: 3 is still on the stack, so it is open and in the same component as 5. low[5] drops to disc[3] = 3.
Edge 5 to open vertex 3, low of 5 is 3.
5 finishes with low[5] = 3 < disc[5] = 5: it reaches an earlier open vertex, so it stays on the stack and will be popped with that vertex's component.
5 stays on the stack.
tarjan(5) returned with low[5] = 3. 5 is still open and reaches earlier, so low[4] drops to 3.
Back in 4, low 3.
Enter 6 at time 6, push it: stack 0 1 2 3 4 5 6. low[6] starts at 6.
Enter 6, pushed.
6 finishes with low[6] = disc[6] = 6: nothing below it reaches an earlier open vertex, so 6 is the root of a component. Pop the stack down to 6: component 1 is {6}.
Component 1: 6.
tarjan(6) returned with low[6] = 6. 6's component is closed already, so low[4] stays 3.
Back in 4, low 3.
4 finishes with low[4] = 3 < disc[4] = 4: it reaches an earlier open vertex, so it stays on the stack and will be popped with that vertex's component.
4 stays on the stack.
tarjan(4) returned with low[4] = 3. low[3] = 3 is already as early, so it stays.
Back in 3, low 3.
3 finishes with low[3] = disc[3] = 3: nothing below it reaches an earlier open vertex, so 3 is the root of a component. Pop the stack down to 3: component 2 is {3, 4, 5}.
Component 2: 3, 4, 5.
tarjan(3) returned with low[3] = 3. 3's component is closed already, so low[2] stays 0.
Back in 2, low 0.
2 finishes with low[2] = 0 < disc[2] = 2: it reaches an earlier open vertex, so it stays on the stack and will be popped with that vertex's component.
2 stays on the stack.
tarjan(2) returned with low[2] = 0. 2 is still open and reaches earlier, so low[1] drops to 0.
Back in 1, low 0.
1 finishes with low[1] = 0 < disc[1] = 1: it reaches an earlier open vertex, so it stays on the stack and will be popped with that vertex's component.
1 stays on the stack.
tarjan(1) returned with low[1] = 0. low[0] = 0 is already as early, so it stays.
Back in 0, low 0.
0 finishes with low[0] = disc[0] = 0: nothing below it reaches an earlier open vertex, so 0 is the root of a component. Pop the stack down to 0: component 3 is {0, 1, 2}.
Component 3: 0, 1, 2.
3 strongly connected components, coloured by membership. Each was popped the moment its root finished, so the components come out in reverse topological order of the condensed graph. One DFS, O(V + E).
3 components.