This is a C++ Program to find the connected components of the undirected graph. This can be done using depth first search algorithm.

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

`#include <iostream>`

`#include <list>`

`#include <stack>`

using namespace std;

`class Graph`

`{`

int V; // No. of vertices

list<int> *adj; // An array of adjacency lists

`// Fills Stack with vertices (in increasing order of finishing times)`

`// The top element of stack has the maximum finishing time`

void fillOrder(int v, bool visited[], stack<int> &Stack);

`// A recursive function to print DFS starting from v`

void DFSUtil(int v, bool visited[]);

public:

Graph(int V);

void addEdge(int v, int w);

`// The main function that finds and prints strongly connected components`

int printSCCs();

`// Function that returns reverse (or transpose) of this graph`

Graph getTranspose();

};

Graph::Graph(int V)

`{`

this->V = V;

adj = new list<int> [V];

`}`

`// A recursive function to print DFS starting from v`

void Graph::DFSUtil(int v, bool visited[])

`{`

`// Mark the current node as visited and print it`

visited[v] = true;

cout << v << " ";

`// Recur for all the vertices adjacent to this vertex`

list<int>::iterator i;

for (i = adj[v].begin(); i != adj[v].end(); ++i)

if (!visited[*i])

DFSUtil(*i, visited);

`}`

Graph Graph::getTranspose()

`{`

Graph g(V);

for (int v = 0; v < V; v++)

`{`

`// Recur for all the vertices adjacent to this vertex`

list<int>::iterator i;

for (i = adj[v].begin(); i != adj[v].end(); ++i)

`{`

g.adj[*i].push_back(v);

`}`

`}`

return g;

`}`

void Graph::addEdge(int v, int w)

`{`

adj[v].push_back(w); // Add w to v’s list.

`}`

void Graph::fillOrder(int v, bool visited[], stack<int> &Stack)

`{`

`// Mark the current node as visited and print it`

visited[v] = true;

`// Recur for all the vertices adjacent to this vertex`

list<int>::iterator i;

for (i = adj[v].begin(); i != adj[v].end(); ++i)

if (!visited[*i])

fillOrder(*i, visited, Stack);

`// All vertices reachable from v are processed by now, push v to Stack`

Stack.push(v);

`}`

`// The main function that finds and prints all strongly connected components`

int Graph::printSCCs()

`{`

stack<int> Stack;

`// Mark all the vertices as not visited (For first DFS)`

bool *visited = new bool[V];

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

visited[i] = false;

`// Fill vertices in stack according to their finishing times`

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

if (visited[i] == false)

fillOrder(i, visited, Stack);

`// Create a reversed graph`

Graph gr = getTranspose();

`// Mark all the vertices as not visited (For second DFS)`

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

visited[i] = false;

int count = 0;

`// Now process all vertices in order defined by Stack`

while (Stack.empty() == false)

`{`

`// Pop a vertex from stack`

int v = Stack.top();

Stack.pop();

`// Print Strongly connected component of the popped vertex`

if (visited[v] == false)

`{`

gr.DFSUtil(v, visited);

cout << endl;

`}`

count++;

`}`

return count;

`}`

`// Driver program to test above functions`

int main()

`{`

`// Create a graph given in the above diagram`

Graph g(5);

g.addEdge(1, 0);

g.addEdge(0, 2);

g.addEdge(2, 1);

g.addEdge(0, 3);

g.addEdge(3, 4);

cout << "Following are strongly connected components in given graph \n";

if (g.printSCCs() > 1)

`{`

cout << "Graph is weakly connected.";

`}`

`else`

`{`

cout << "Graph is strongly connected.";

`}`

return 0;

`}`

Output:

$ g++ StronglyWeaklyConnectedGraph.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.**

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

» Next Page - C++ Program to Apply DFS to Perform the Topological Sorting of a Directed Acyclic Graph