So, that's going to be the current leader because that's where
the current DFS got initiated.
Now, from 9, there's only one choice.
We have to go to 7.
From 7, there's only one choice, we have to go to 8.
From 8, there's only one choice, we have to go back to 9.
And then, 9's already been seen, so we backtrack.
We go back to 8, we go back to 7, we go back to 9, and that's it.
So, when we invoke DFS for node 9,
the only things that we encounter are, the nodes 7, 8, and 9.
And these are all going to be given the leader vertex 9.
You will notice that this is indeed one
of the strongly connected components of the graph.
We just sort of found it with this indication of DFS from the node 9.
So, now we go back to the outer for loop.
And we say, okay, let's go to node 8, have we already seen 8?
Yes.
What about 7, have we already seen 7?
Yes.
What about 6?
Have we have already seen 6?
We have not, we have not yet discovered 6, so
we invoke DFS from node 6, we reset the global source vortex s to 6.
From 6, we can go to 9, we can go to 1.
So, let's say we explore 9 first.
Well, we already saw 9 in an earlier iteration in the for loop, so
we don't explore it again, so, we don't discover 9 now, so we backtrack to 6.
We go to 1, from 1, we have to go to 5, and 5 we have to go to 6,
and then we start backtracking again.
So, the only new nodes that we encounter when we invoke DFS
from the node 6 are the vertices 6, 1, and 5.
And all of these will have a leader vertex of
6 because that's where we called DFS from when we first discovered these 3 nodes.
And you'll notice, this is another FCC of this directed graph.
So, we invoke DFS again, not from a new node, the new node 6.
And what it discovered,
the new nodes it discovered was exactly an FCC of the graph.
Nothing more, nothing less.
So, now we return to the outer for loop, we go to node 5, have we already seen 5?
Yes.
Have we already seen 4?
No, we haven't seen 4 yet.
So, now we invoke DFS from 4.
Again, we could try to explore 5, but we've seen that before,
we're not going to explore it again.
So from 4 then, we have to go to 2, from 2 we have to go to 3,
from 3 have to go back to 4, and then, after all the backtracking, we're done.
So, the final call to DFS will be from the node 4.