Finding Strongly Connected Components of a
             Directed Graph by Using Depth First Search Twice

We are given a directed graph G.  We must be able to create arrays
indexed by the set of nodes, and we must be able to access the set of
in-neighbors and the set of out-neighbors of any node.

We can assume that our nodes are initially given to us as x_1, ... x_n.
This initial ordering of the nodes is arbitrary, i.e., the correctness
of the algorithm does not depend on the initial ordering.

1.  Create an array of type boolean, indexed by the set of nodes.
Set its value to "false" for each node.  We call this the "visited"
bit of a node.

2.  Create an array of type integer, indexed by the set of nodes.
Do not initialize the values.  A value in this array will be called
the "finishing time" of a node.

3.  Create an array of type node, indexed by the set of nodes.  The
value for each node will be the "leader" of the strong component
containing that node.  That is, when we are done, the nodes of G
will be partitioned into strong components, each of which has a "leader"
node.  If x is a node, then leader(x) is the leader of the strong component
containing x.  Thus, for example, if x is a leader, then leader(x) = x.
We do not initialize the array "leader."

4.  We need a stack, S, to implement DFS.

 ----------------------------------------------------------------------
 ----------------------------------------------------------------------
The Algorithm.

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.

Reverse all the edges in the graph, i.e., an edge from x to y
becomes an edge from y to x.

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

 ----------------------------------------------------------------------
 ----------------------------------------------------------------------