# Kosaraju’s Algorithm for Strongly Connected Components(SCC)

Problem Statement: Given a Directed Graph with V vertices (Numbered from 0 to V-1) and E edges, Find the number of strongly connected components in the graph.

Example:

Input: Output: Explanation: The idea behind SCC is that if we start from any node in a component, we must be able to reach all other nodes in that component. Note that by components here, we mean that we group certain nodes in the graph that meet the condition for every node in that component. The marked components in the following graph are from an SCC.

## Solution

Intuition: The idea behind KosaRaju’s algorithm is to do a DFS in a controlled fashion such that we won’t be able to go from one SCC to other. One DFS call would visit all the nodes in an SCC only.

Approach :

• Sort all the nodes according to their topo sort(loosely based topo sort as we may have cycles here)
• Transpose the graph i.e reverse all the edges of the graph
• Use the topo sort or the increasing order of finishing time to find the strongly connected components using DFS.
• Following is the demonstration of the above algorithm: Code:

## C++ Code

``````#include <bits/stdc++.h>
using namespace std;
void dfs(int node, stack<int> &st, vector<int> &vis, vector<int> adj[]) {
vis[node] = 1;
if(!vis[it]) {
}
}

st.push(node);
}
void revDfs(int node, vector<int> &vis, vector<int> transpose[]) {
cout << node << " ";
vis[node] = 1;
for(auto it: transpose[node]) {
if(!vis[it]) {
revDfs(it, vis, transpose);
}
}
}
int main() {
int n=6, m=7;

stack<int> st;
vector<int> vis(n+1, 0);
for(int i = 1;i<=n;i++) {
if(!vis[i]) {
}
}

vector<int> transpose[n+1];

for(int i = 1;i<=n;i++) {
vis[i] = 0;
transpose[it].push_back(i);
}
}

while(!st.empty()) {
int node = st.top();
st.pop();
if(!vis[node]) {
cout << "SCC: ";
revDfs(node, vis, transpose);
cout << endl;
}
}

return 0;
}
``````

Output:

SCC: 1 2 3
SCC: 5 6 4

Time Complexity: O(N+E), DFS+TopoSort

Space Complexity: O(N+E), Transposing the graph

## Java Code

``````import java.util.*;

class Main
{
private void dfs(int node, Stack<Integer> st, ArrayList<ArrayList<Integer>> adj, int vis[]) {
vis[node] = 1;
if(vis[it] == 0) {
}
}

st.push(node);
}

private void revDfs(int node, ArrayList<ArrayList<Integer>> transpose, int vis[]) {
vis[node] = 1;
System.out.print(node + " ");
for(Integer it : transpose.get(node)) {
if(vis[it] == 0) {
revDfs(it, transpose, vis);
}
}
}

{
int vis[] = new int[n];
Stack<Integer> st = new Stack<Integer>();
for(int i = 0;i<n;i++) {
if(vis[i] == 0) {
}
}

ArrayList<ArrayList<Integer> > transpose = new ArrayList<ArrayList<Integer> >();

for (int i = 0; i < n; i++)

for(int i = 0;i<n;i++) {
vis[i] = 0;
}
}

while(st.size() > 0) {
int node = st.peek();
st.pop();
if(vis[node] == 0) {
System.out.print("SCC: ");
revDfs(node, transpose, vis);
System.out.println();
}
}

}
public static void main(String args[])
{
int n = 7;
ArrayList<ArrayList<Integer> > adj = new ArrayList<ArrayList<Integer> >();

for (int i = 0; i < n; i++)

Main obj = new Main();

}
}
``````

Output:

SCC: 1 2 3
SCC: 5 6 4

Time Complexity: O(N+E), DFS+TopoSort

Space Complexity: O(N+E), Transposing the graph