finding strong components by performing two depth-first searcheswe can test whether directed graph is strongly connectedand if it is notwe can actually produce the subsets of vertices that are strongly connected to themselves this can also be done in only one depth-first searchbut the method used here is much simpler to understand firsta depth-first search is performed on the input graph the vertices of are numbered by postorder traversal of the depth-first spanning forestand then all edges in are reversedforming gr the graph in figure represents gr for the graph shown in figure the vertices are shown with their numbers the algorithm is completed by performing depth-first search on gr always starting new depth-first search at the highest-numbered vertex thuswe begin the depth-first search of gr at vertex gwhich is numbered this leads nowhereso the next search is started at this call visits and the next call starts at and visits acand the next calls after this are dfs(dand finally dfs(ethe resulting depth-first spanning forest is shown in figure each of the trees (this is easier to see if you completely ignore all nontree edgesin this depth-first spanning forest forms strongly connected component thusfor our examplethe strongly connected components are { }{hij}{bacf}{ }and {eto see why this algorithm worksfirst note that if two vertices and are in the same strongly connected componentthen there are paths from to and from to in the original graph gand hence also in gr nowif two vertices and are not in the same depth-first spanning tree of gr clearly they cannot be in the same strongly connected component , , , , , , , , , , figure gr numbered by postorder traversal of (from fig