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.

// Implementation of Kosaraju's algorithm to print all SCCs

```
#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";

```
    g.printSCCs();
```
```
    return 0;
```
```
}
```

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.

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]

« Prev - C++ Program to Implement Dijkstra’s Algorithm using Queue

» Next - C++ Program to Find the Transitive Closure of a Graph using Warshall’s Algorithm

Related Posts:

Recommended Articles: