So This article is about strongly connected Graph. ?

Prerequisite for the implementation:-

1.Familiar with Graph and adjacency list.

2. What is strongly Connected graph??

2. knowledge of Depth first Search.

3. Topological sort.

First What is Strongly Connected Node??

The collection of node is called strongly connected if we choose any pair of vertices we would we able to reach that vertices from the given one.

Now Comes to the Algorithmic part:-

Basically there is three step to find the strongly connected component:-

- first do topological sort of the graph.

How to implement this part:-

first create a stack.

Now for every node do dfs traversal.

and after each recursion call simply push that node into stack.

it will look like:-

Dfs(u, adj,stack, visited)

{

mark u visited.

now go for all the adjacent of u and if it not visited

call Dfs(adjacent of u, adj,stack,visited)

s.push(u);

}

After this step.

Step 2.

Reverse all the edges the reason is that after reversing all the edges of SCC will remain Scc.

Step 3.

Now simply call dfs until the stack is empty in the same way for each node we have obtained in the stack. and upto where we reach from that node we take that node in the scc component and mark it visited.

repeat this until stack is not empty.

So finally we got the strongly connected component.

for ex:-

2

5

5

0 1

1 2

2 0

1 3

3 4

4

4

0 1

1 2

1 3

3 0

output:-

Following are strongly connected components:-

0 2 1

3

4

The number of scc is:- 3

Following are strongly connected components:-

0 3 1

2

The number of scc is:- 2

Thatâ€™s all I have got. Rest you all guys suggest if i have done any mistakes in the above algorithm.