**What is a strongly connected component?**

A strongly connected component or SCC of a directed graph is a **maximal set of vertices’s in which there is a path from any one vertex to any other vertex in the set**. Or in other words it is a **maximal strongly connected subgraph***.*

Finding strongly connected components is a simple application of Depth First Search in Directed graphs.

For example **there are 3 SCC in the given graph**

**Reverse/Transpose graph**: It is a *directed graph with the direction of all its edges reversed.* This usually comes handy while dealing with problems involving topological sort.

We can find all SCC using **Kosaraju’s 2 pass algorithm** for finding the strongly connected component in a directed graph in **O(n+m) time complexity**. I prefer this algorithm because it is prevalent and quite easy to understand and code as well in programming contest environment.

**Kosaraju’s algorithm** is as follows:

- Let G be a directed graph and S be an empty stack.
- While S does not contain all vertices:
- Choose an arbitrary vertex
*v*not in S. Perform a depth-first search starting at*v*. Each time that depth-first search finishes expanding a vertex*u*, push*u*onto S.

- Choose an arbitrary vertex
- Reverse the directions of all arcs to obtain the transpose graph.
- While S is nonempty:
- Pop the top vertex
*v*from S. Perform a depth-first search starting at*v*in the transpose graph. The set of visited vertices will give the strongly connected component containing*v*; record this and remove all these vertices from the graph G and the stack S. Equivalently, breadth-first search (BFS) can be used instead of depth-first search.

- Pop the top vertex

The **main idea** for using transpose graphs in this algorithm is

Graphs G and G’ have the same SCC’s

Also , the *SCC component graph is a directed acyclic graph.*

*The C++ implementation to the above algorithm can be found here.*

**Problems to try:**

SPOJ – WEBISL

SPOJ – CAPCITY

SPOJ – BOTTOM

SPOJ – TPCPPLAR

Codeforces Round#244 Div2 C

**References:**

Kosaraju algorithm Wikipedia

Strongly connected component geeksforgeeks.org