Increment a single clock on each discovery and finish, starting with clock zero. Lexicographic depth-first search givesThe first search tree has discovery edges , , . The edge returns to an active ancestor. Once that tree finishes, vertex is a new root whose neighbour is already finished, and vertex is the final root. This accounts for all twelve events in the DFS discovery and finishing times.
The only possibilities are . Vertex reaches all of . In depth-first search, all vertices reachable from an active vertex must have been discovered and finished before its own finishing event, except for active ancestors. None of these four can be an ancestor of , because none can reach . Thus all four are finished before finishes.
Vertex cannot already be finished at that point: its outgoing edge to would have caused to be visited before it could finish. It also cannot be a descendant of , since cannot reach . Therefore is either still undiscovered or an active ancestor. In the first case the only remaining events are discovery and finishing of , giving . In the second case the only remaining event is finishing of , giving .
Both occur. Starting the outer traversal with leaves undiscovered and gives time . Starting with and taking its edge to first makes an ancestor and gives time . The argument does not assume any particular order on the other edges.
The strongly connected components areThe directed cycle makes its three vertices mutually reachable. Vertex has no outgoing edge. Vertex reaches that cycle but has no return path from it, and vertex reaches the other components but has no incoming path from them. These facts exclude every further merger.
Articles by others on the same topic
There are currently no matching articles.