C++ Program to Check if a Graph is Strongly Connected or Not

This is a C++ Program to check whether given graph is strongly connected or not. If there exists multiple strongly connected component, graph is not strongly connected, it is otherwise.

Here is source code of the C++ Program to Check Whether a Graph is Strongly Connected or Not. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. // Implementation of Kosaraju's algorithm to print all SCCs
  2. #include <iostream>
  3. #include <list>
  4. #include <stack>
  5. using namespace std;
  6.  
  7. class Graph
  8. {
  9.         int V; // No. of vertices
  10.         list<int> *adj; // An array of adjacency lists
  11.  
  12.         // Fills Stack with vertices (in increasing order of finishing times)
  13.         // The top element of stack has the maximum finishing time
  14.         void fillOrder(int v, bool visited[], stack<int> &Stack);
  15.  
  16.         // A recursive function to print DFS starting from v
  17.         void DFSUtil(int v, bool visited[]);
  18.     public:
  19.         Graph(int V);
  20.         void addEdge(int v, int w);
  21.  
  22.         // The main function that finds and prints strongly connected components
  23.         int printSCCs();
  24.  
  25.         // Function that returns reverse (or transpose) of this graph
  26.         Graph getTranspose();
  27. };
  28.  
  29. Graph::Graph(int V)
  30. {
  31.     this->V = V;
  32.     adj = new list<int> [V];
  33. }
  34.  
  35. // A recursive function to print DFS starting from v
  36. void Graph::DFSUtil(int v, bool visited[])
  37. {
  38.     // Mark the current node as visited and print it
  39.     visited[v] = true;
  40.     cout << v << " ";
  41.  
  42.     // Recur for all the vertices adjacent to this vertex
  43.     list<int>::iterator i;
  44.     for (i = adj[v].begin(); i != adj[v].end(); ++i)
  45.         if (!visited[*i])
  46.             DFSUtil(*i, visited);
  47. }
  48.  
  49. Graph Graph::getTranspose()
  50. {
  51.     Graph g(V);
  52.     for (int v = 0; v < V; v++)
  53.     {
  54.         // Recur for all the vertices adjacent to this vertex
  55.         list<int>::iterator i;
  56.         for (i = adj[v].begin(); i != adj[v].end(); ++i)
  57.         {
  58.             g.adj[*i].push_back(v);
  59.         }
  60.     }
  61.     return g;
  62. }
  63.  
  64. void Graph::addEdge(int v, int w)
  65. {
  66.     adj[v].push_back(w); // Add w to v’s list.
  67. }
  68.  
  69. void Graph::fillOrder(int v, bool visited[], stack<int> &Stack)
  70. {
  71.     // Mark the current node as visited and print it
  72.     visited[v] = true;
  73.  
  74.     // Recur for all the vertices adjacent to this vertex
  75.     list<int>::iterator i;
  76.     for (i = adj[v].begin(); i != adj[v].end(); ++i)
  77.         if (!visited[*i])
  78.             fillOrder(*i, visited, Stack);
  79.  
  80.     // All vertices reachable from v are processed by now, push v to Stack
  81.     Stack.push(v);
  82. }
  83.  
  84. // The main function that finds and prints all strongly connected components
  85. int Graph::printSCCs()
  86. {
  87.     stack<int> Stack;
  88.  
  89.     // Mark all the vertices as not visited (For first DFS)
  90.     bool *visited = new bool[V];
  91.     for (int i = 0; i < V; i++)
  92.         visited[i] = false;
  93.  
  94.     // Fill vertices in stack according to their finishing times
  95.     for (int i = 0; i < V; i++)
  96.         if (visited[i] == false)
  97.             fillOrder(i, visited, Stack);
  98.  
  99.     // Create a reversed graph
  100.     Graph gr = getTranspose();
  101.  
  102.     // Mark all the vertices as not visited (For second DFS)
  103.     for (int i = 0; i < V; i++)
  104.         visited[i] = false;
  105.     int count = 0;
  106.     // Now process all vertices in order defined by Stack
  107.     while (Stack.empty() == false)
  108.     {
  109.         // Pop a vertex from stack
  110.         int v = Stack.top();
  111.         Stack.pop();
  112.  
  113.         // Print Strongly connected component of the popped vertex
  114.         if (visited[v] == false)
  115.         {
  116.             gr.DFSUtil(v, visited);
  117.             cout << endl;
  118.         }
  119.         count++;
  120.     }
  121.     return count;
  122. }
  123.  
  124. // Driver program to test above functions
  125. int main()
  126. {
  127.     // Create a graph given in the above diagram
  128.     Graph g(5);
  129.     g.addEdge(1, 0);
  130.     g.addEdge(0, 2);
  131.     g.addEdge(2, 1);
  132.     g.addEdge(0, 3);
  133.     g.addEdge(3, 4);
  134.  
  135.     cout << "Following are strongly connected components in given graph \n";
  136.     g.printSCCs();
  137.     return 0;
  138. }

Output:

$ g++ CheckStronglyConnected.cpp
$ a.out
 
Following are strongly connected components in given graph 
0 1 2 
3 
4 
Graph is weakly connected.
 
------------------
(program exited with code: 0)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
advertisement

Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.