Check if a graph is a strongly connected using Kosaraju DFS algorithm

Problem Statement:

You are given a directed graph, you need to find out if the graph is strongly connected or not.

A strongly connected garph if there is a path between any two pair of vertices.

Solution

Step 1: Take an array to hold if a vertex has been visited or not.

Step 2: Do a DFS traversal starting from any vertex and if DFS traversal doesn’t visit all vertices, then we return false.

Step 3: Reverse the edges of all the nodes.

Step 4: Do a DFS traversal of the reversed graph starting from the same vertex used in step 2.

Step 5: If DFS doesn’t visit all the vertices, then return false.

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <unordered_set> 
#include <list> 

using namespace std;

class Graph
{

private:
   int V; 
   list<int> *adj; // to hold adjacency list
   void helper(int v, bool visited[]); 
   Graph* reverse_graph();

public:
   Graph(int V); // Constructor
   void add_edge(int v, int w); // to add an edge to graph
   bool check_if_graph_is_strongly_connected(); 
};

Graph::Graph(int V)
{
   // get the total number of nodes
   this->V = V;

   // initialize adjacency list for that number of nodes
   adj = new list<int>[V];
}

void Graph::add_edge(int v, int w)
{
   // add the edge to adjacency list
   adj[v].push_back(w); 
   //adj[w].push_back(v); 
}


void Graph::helper(int v, bool visited[])
{
      visited[v] = true;

      for(auto i = adj[v].begin(); i != adj[v].end(); i++)
      {
         int adjVertex = *i;

         if ( !visited[adjVertex]){
             helper(adjVertex, visited);
         }
      }
}

Graph* Graph::reverse_graph()
{
   Graph *rev_graph = new Graph(V);

   for(int i = 0; i < V; i++)
   {
      for(auto j = adj[i].begin(); j != adj[i].end(); j++)
      {
         rev_graph->adj[*j].push_back(i);
      }
   }
   return rev_graph;
}


bool Graph::check_if_graph_is_strongly_connected()
{
   bool *visited = new bool[V];
   for(int i = 0; i < V; i++)
   {
      visited[i] = false;
   }

   //do DFS traversal from node 0 
   helper(0, visited);

   // if DFS traversal did not visit all the nodes, then return false.
   for (int i = 0; i < V; i++)
      if (visited[i] == false)
         return false;

   //reverse the graph
   Graph *reverse = reverse_graph();

   //reset the visited matrix
   for(int i = 0; i < V; i++)
   {
      visited[i] = false;
   }

   //do a DFS traversal for reversed matrix
   reverse->helper(0, visited);

   // if DFS traversal did not visit all the nodes, then return false.
   for (int i = 0; i < V; i++)
      if (visited[i] == false)
         return false;

   return true;

}


int main()
{

   Graph g(5);
   g.add_edge(0, 1);
   g.add_edge(1, 2);
   g.add_edge(2, 3);
   g.add_edge(3, 0);
   g.add_edge(2, 4);
   g.add_edge(4, 2);

   if(g.check_if_graph_is_strongly_connected()){
      cout<<"The graph is strongly connected"<<endl;
   } else {
      cout<<"The graph is not strongly connected"<<endl;
   }
   return 0;
}

Output:

The graph is strongly connected