Strongly Connected Components

Strongly connected components of a graph are Strongly Connected Graph sections of a graph which are separated only by unidirectional (only able to travel in one direction) edges.

For example, in the graph below there are two strongly connected components because the left and right side only have connections moving from left to right, but there is no way to get from right to left.

Pasted image 20240420233651.png

Algorithm

See: DFS, and Transpose Graph ()

  1. Call to compute finishing times for each Vertex .
  2. Compute
  3. Call again, bit in the main loop of DFS, consider the Vertex in order of decreasing .
  4. Output the vertices of each tree in the DFS Forest formed in line 3 as a separate strongly connected component.

Time complexity:  because for each pair of vertices we are checking whether a path exists between them.