« back

Strongly Connected Components (Kosaraju's Algo)

Tags : graph, dfs, geeksforgeeks, cpp, medium

Problem Statement - link #

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.

Your Task:

You don’t need to read input or print anything. Your task is to complete the function kosaraju() which takes the number of vertices V and adjacency list of the graph as inputs and returns an integer denoting the number of strongly connected components in the given graph.

Expected Time Complexity: O(V+E)
Expected Auxiliary Space: O(V)

Examples #

Example 1:

Output:
3
Explanation:


We can clearly see that there are 3 Strongly
Connected Components in the Graph

Constraints #

Solutions #

class Solution
{
    public:
	void fillOrder(int s, vector<int> adj[],bool vis[],stack<int>&st){
	    vis[s]=1;
        for(int i: adj[s])
            if(!vis[i])
                fillOrder(i,adj,vis,st);
	    st.push(s);
	}
	vector<int>* transpose(int V,vector<int> adj[]){
        vector<int> *tv = new vector<int>[V];
        for(int v=0;v<V;v++)
            for(int u: adj[v])
                tv[u].push_back(v);
	    return tv;
	    
	}
	void dfs(int s,vector<int> adj[],bool vis[]){
	    vis[s]=1;
	    for(int v:adj[s])
	        if(!vis[v])
	            dfs(v,adj,vis);
	}
	//Function to find number of strongly connected components in the graph.
    int kosaraju(int V, vector<int> adj[])  {
        //code here
        bool vis[V]={0};
        stack<int> st;
        for(int i=0;i<V;i++)
            if(!vis[i])
                fillOrder(i,adj,vis,st);
        vector<int> *tv = transpose(V,adj);
        fill(vis,vis+V,0);
        int res=0;
        while(!st.empty()){
            int s=st.top(); st.pop();
            if(!vis[s])
                {dfs(s,tv,vis);res++;}
        }
        return res;
    }
};