DFS is broken into "phases." At the beginning and the end of each phase, the stack is empty. During each phase, we visit one or more nodes. We assume that there is an "initial order" of the nodes, and when the stack is empty, we start the new phase with the "first" unvisited node. The basic idea is to execute DFS twice. During the first execution, each node x is labeled with a finishing_time, that being the value of the clock at the point that we know we have finished visiting all nodes reachable from x. In the second excution of DFS, we first sort the nodes in reverse order, using the finishing times, and that becomes our new initial ordering. Each time we visit a node, we assign its leader to be the first node we visited in that phase. Each phase ends when the stack is empty. ---------------------------------------------------------------------- 1. Initialize the array "visited" to false for every node. 2. Let t := 0. (t is the "clock.") 3. S := empty stack. 4. For i from 1 to n, execute the following: If not visited(x_i) then execute the following: %% NEW PHASE a. visited(x_i) := true. b. push x_i onto S. c. while S is not empty, execute the following loop: i. Let y = top(S). (This is peeking!) ii. If y has no unvisited out-neighbors then t := t+1 finishing_time(y) := t pop (i.e., delete y from S) else let z := any unvisited out-neighbor of y visited(z) := true push z onto S 5. Sort the nodes in reverse order by finishing time. That is, we will relabel the nodes as x_1, ... x_n, where finishing_time(x_i) > finishing_time(x_j) if i < j. 6. Re-initialize "visited" to be false for every node. 7. S := empty stack. 8. For i from 1 to n, execute the following: If not visited(x_i) then execute the following: %% NEW STRONG COMPONENT a. leader(x_i) := x_i b. visited(x_i) := true. c. push x_i onto S. d. while S is not empty, execute the following loop: i. Let y = top(S). (This is peeking!) ii. If y has no unvisited out-neighbors then pop (i.e., delete y from S) else let z := any unvisited out-neighbor of y visited(z) := true leader(z) := x_i push z onto S ---------------------------------------------------------------------- ----------------------------------------------------------------------