## Problem Statement

Find all strongly connected components in O(V+E) time using Kosaraju’s algorithm.

**Strongly connected Component(SCC) –** In a directed graph a strongly connected component is a component of the graph in which there is a path between every pair of vertices.

## Example

Example of strongly connected component in a graph :

## Example Explanation

In the above Example diagram the directed graph contains three strongly connected component.

- the vertex group of (7,5,6) in which there is a path between every pair of vertices.
- 4 – single vertex
- The vertex group of (1,2,3) in which there is a path between every pair of vertices.

In the above example we can see that a single vertex is also considered as a strongly connected component. As kosaraju Algorithm finds the minimum number of strongly connected component in directed graph so the answer to the above example will be 3.

## Input/Output

**Input –** Given Number of vertices = N, and number of edges of the directed graph = M and the weight of the M edges.

**Output –** Number of strongly connected component in the given directed graph.

## Kosaraju’s Algorithm

**Intution –** The intution behind Koasaraju algorithm is to perform DFS in the directed graph such that one DFS call would be able visit all the vertices of a strongly connected component in the graph.

**Algorithm Steps :**

- Depth First traversal(DFS) is done on the graph and when DFS traversal is done recursively on adjacent vertex of the graph, the vertex are pushed to an empty stack one by one.
- Find the transpose of the graph by reversing the direction of every edge in the directed graph.
- Pop the vertex from the stack one by one and do DFS on the popped out vertex “v”. The DFS will print the stronlgy connected component of “v”.

**Implementaion in C++ :**

```
#include <bits/stdc++.h>
using namespace std;
class DirectedGraph{
int V;
```*// total no of vertices in graph*
list<int> *Arr; *// An array of adjacency lists to represent the graph*
*// function to fill the stack with vertices in correct order of finishing time*
void fillInCorrectOrder(int v, bool isVisited[], stack<int> &Stack);
*// function to apply DFS in vertex of the graph*
void DFSOnVertex(int v, bool isVisited[]);
public:
DirectedGraph(int V);
void addEdgeWithWeight(int v, int w);
*// function to print the strongly connected component in graph*
void printStronglyConnectedComponent();
*// Funtion to reverse the arrow direction in the directed graph*
DirectedGraph getTranspose();
};
*// function to create graph with vertex V*
DirectedGraph::DirectedGraph(int V){
this->V = V;
Arr = new list<int>[V];
}
*// A recursive function to print DFS starting from v*
void DirectedGraph::DFSOnVertex(int v, bool isVisited[]){
*// Mark the current node as visited and print it*
isVisited[v] = true;
cout << v << " ";
list<int>::iterator it;
for (it = Arr[v].begin(); it != Arr[v].end(); ++it){
if (!isVisited[*it])
DFSOnVertex(*it, isVisited);
}
}
DirectedGraph DirectedGraph::getTranspose(){
DirectedGraph original_graph(V);
for (int v = 0; v < V; v++){
list<int>::iterator it;
for(it = Arr[v].begin(); it != Arr[v].end(); ++it){
original_graph.Arr[*it].push_back(v);
}
}
return original_graph;
}
void DirectedGraph::addEdgeWithWeight(int v, int weight){
Arr[v].push_back(weight); *// push the weight to the array *
}
void DirectedGraph::fillInCorrectOrder(int v, bool isVisited[], stack<int> &Stack){
*// current node is marked visited initially*
isVisited[v] = true;
*// iterate over all the vertices and check if its visited or not.*
list<int>::iterator it;
for(it = Arr[v].begin(); it != Arr[v].end(); ++it)
if(!isVisited[*it])
fillInCorrectOrder(*it, isVisited, Stack);
*// push the vertices visited in the stack*
Stack.push(v);
}
*// function to print the strongly connected components*
void DirectedGraph::printStronglyConnectedComponent(){
stack<int> Stack;
*// Mark all the vertices as not visited (For first DFS)*
bool *isVertexVisited = new bool[V];
for(int j = 0; j < V; j++)
isVertexVisited[j] = false;
for(int j = 0; j < V; j++)
if(isVertexVisited[j] == false)
fillInCorrectOrder(j, isVertexVisited, Stack);
*// transpose of the graph*
DirectedGraph reverse_graph = getTranspose();
*// in second DFS mark all vertices as not visited*
for(int j = 0; j < V; j++)
isVertexVisited[j] = false;
*// check for all vertices in the stack*
while (Stack.empty() == false){
int v = Stack.top();
Stack.pop();
if (isVertexVisited[v] == false){
reverse_graph.DFSOnVertex(v, isVertexVisited);
cout << endl;
}
}
}
int main(){
*// Create a graph given *
DirectedGraph original_graph(5);
original_graph.addEdgeWithWeight(1, 0);
original_graph.addEdgeWithWeight(0, 2);
original_graph.addEdgeWithWeight(2, 1);
original_graph.addEdgeWithWeight(0, 3);
original_graph.addEdgeWithWeight(3, 4);
cout << "SCC in the given graph \n";
original_graph.printStronglyConnectedComponent();
return 0;
}

**Impelementation in Java :**

```
import java.io.*;
import java.util.*;
import java.util.LinkedList;
class Graph{
private int V;
```*// Total no of vertices in the graph*
private LinkedList<Integer> Arr[]; *// representation of graph as adjacency list*
Graph(int vertex){
V = vertex;
Arr = new LinkedList[vertex];
for (int i=0; i<vertex; ++i)
Arr[i] = new LinkedList();
}
*//function to create graph by adding edge to the graph*
void addEdgeWithWeight(int v, int weight){
Arr[v].add(weight);
}
*// function to apply DFS on the vertex of the graph recursively*
void DFSOnVertex(int v, boolean isVisited[]){
*// initially the current node is marked visited in the graph*
isVisited[v] = true;
System.out.print(v + " ");
int next;
*// check for all the vertices adjacent to the current verices*
Iterator<Integer> i =Arr[v].iterator();
while (i.hasNext()){
next = i.next();
if (!isVisited[next])
DFSOnVertex(next,isVisited);
}
}
*//function to create transpose of the graph *
Graph getTranspose(){
Graph original_graph = new Graph(V);
for (int v = 0; v < V; v++){
*// check for all the vertex adjacent to the current vertex*
Iterator<Integer> it =Arr[v].listIterator();
while(it.hasNext())
original_graph.Arr[it.next()].add(v);
}
return original_graph;
}
void fillInCorrectOrder(int v, boolean isVisited[], Stack stack){
*// current node is marked visited initially*
isVisited[v] = true;
*// Recur for all the vertices adjacent to this vertex*
Iterator<Integer> it = Arr[v].iterator();
while (it.hasNext()){
int next = it.next();
if(!isVisited[next])
fillInCorrectOrder(next, isVisited, stack);
}
*// push the vertices to the stack*
stack.push(new Integer(v));
}
*// funciton to print the strongly connected component in the graph*
void printStronglyConnectedComponents(){
Stack stack = new Stack();
*// for second DFS all the vertices are marked not visited*
boolean isVertexVisited[] = new boolean[V];
for(int j = 0; j < V; j++)
isVertexVisited[j] = false;
*// fill the stack with vertices based on finising time*
for (int j = 0; j < V; j++)
if (isVertexVisited[j] == false)
fillInCorrectOrder(j, isVertexVisited, stack);
*// to create transpose of the graph*
Graph reverse_graph = getTranspose();
*// In the second DFS all the vertices are marked non visited*
for (int j = 0; j < V; j++)
isVertexVisited[j] = false;
*// process all the vertices in the stack in order of finishing time*
while (stack.empty() == false){
int v = (int)stack.pop();
if (isVertexVisited[v] == false){
reverse_graph.DFSOnVertex(v, isVertexVisited);
System.out.println();
}
}
}
public static void main(String args[]){
*// Create a graph *
Graph original_graph = new Graph(5);
original_graph.addEdgeWithWeight(1, 0);
original_graph.addEdgeWithWeight(0, 2);
original_graph.addEdgeWithWeight(2, 1);
original_graph.addEdgeWithWeight(0, 3);
original_graph.addEdgeWithWeight(3, 4);
System.out.println("SCC in the given graph \n");
original_graph.printStronglyConnectedComponents();
}
}

**Implementaion in Python :**

```
from collections import defaultdict
class Graph:
def __init__(self,vertices):
self.V= vertices
```*#Total no of verices in the graph*
self.graph = defaultdict(list) *# to store the graph in a dictionary*
*# function to create graph by adding edge of the graph*
def addEdge(self,u,v):
self.graph[u].append(v)
*# function to apply DFS on the vertex*
def DFSOnVertex(self,v,isVisited):
*# Mark the current node as visited and print it*
isVisited[v]= True
print(v, end=" ")
*#Recur for all the vertices adjacent to this vertex*
for i in self.graph[v]:
if isVisited[i]==False:
self.DFSOnVertex(i,isVisited)
def fillInCorrectOrder(self,v,isVisited, stack):
*# Mark the current node as visited*
isVisited[v]= True
*# Recur for all the vertices adjacent to this vertex*
for i in self.graph[v]:
if isVisited[i]==False:
self.fillInCorrectOrder(i, isVisited, stack)
stack = stack.append(v)
*# function to get transpose of the graph*
def getTranspose(self):
original_graph = Graph(self.V)
*# check and recursively cal for all the adjacent verices*
for i in self.graph:
for j in self.graph[i]:
original_graph.addEdge(j,i)
return original_graph
*# function to print all strongly connected component in the graph*
def printStronglyConnectedComponents(self):
stack = []
*# initally all the vertices are marked not visited in second DFS round*
isVisited =[False]*(self.V)
*# fill the stack with vertices in the order of finisshing time.*
for i in range(self.V):
if isVisited[i]==False:
self.fillInCorrectOrder(i, isVisited, stack)
*# tranpose of the graph*
gr = self.getTranspose()
*# initally all the vertices are marked not visited in second DFS round*
isVisited =[False]*(self.V)
*# process the vertices in the stack infincshing time order*
while stack:
i = stack.pop()
if isVisited[i]==False:
gr.DFSOnVertex(i, isVisited)
print("")
*# Create a graph given *
original_graph = Graph(5)
original_graph.addEdge(1, 0)
original_graph.addEdge(0, 2)
original_graph.addEdge(2, 1)
original_graph.addEdge(0, 3)
original_graph.addEdge(3, 4)
print ("SCC in the given graph ")
original_graph.printStronglyConnectedComponents()

**Output of All Above Programs:**

```
SCC in the given graph
0 1 2
3
4
```

**Time Complexity** : In kosaraju algorithm mainly three steps takes place :

**DFS is called :**Time taken to perform DFS on graph represented by adjacency list is O(V+E).- graph represented by adjacency list is reversed: For reversing the graph represented using adjacency list we have to iterate over the adjacency list which will take O(V) time.
**Again DFS is called :**TIme taken for DFS on graph represented by adjacecny list is O(V+E)

So, the total time taken in all the three steps in kosaraju algorithm is O(V+E) +O(V) +O(V+E) = O(V+E)

So, the time comlexity of the kosaraju algorithm is **O(V+E)**.

**Space Complexity** : As kosaraju algorithm uses stack to store the vertices while performing first DFS so the space used by stack is equal to size of the vertices of the graph. So, the time complexity of kosaraju’s algorithm is **O(N)**, where N is the total no of vertices in the graph.

## Strongly Connected Components Applications

- Strongly connected components SCC are used in social media algorithms where SCC is used to know the persons with common interest and common friends.
- Strongly connected components are used in maps algorithm to link the path with similar origin and destination.
- Strongly connected components are also used in vehicle routing algorithms.

## Conclusion

- Strongly connected components are group of vertices in a directed graph in which every vertex has a path to the other vertices in that component.
- Kosaraju algorithm is used to find the number of strongly component in a directed graph using DFS on the graph.
- SCC is used in social media applications to link people with common interest.
- SCC is used in maps algorithm
- SCC is used in vehicle routing algorithm.