C++ Program to Find Strongly Connected Components in Graphs

Weakly or Strongly Connected for a given a directed graph can be found out using DFS. This is a C++ program of this problem.

Functions used

Begin Function fillorder() = fill stack with all the vertices.    a) Mark the current node as visited and print it    b) Recur for all the vertices adjacent to this vertex    c) All vertices reachable from v are processed by now, push v to Stack End Begin Function DFS() :    a) Mark the current node as visited and print it    b) Recur for all the vertices adjacent to this vertex End

Example

#include <iostream> #include <list> #include <stack> using namespace std; class G {    int m;    list<int> *adj;    //declaration of functions    void fillOrder(int n, bool visited[], stack<int> &Stack);    void DFS(int n, bool visited[]);    public:    G(int N); //constructor    void addEd(int v, int w);    int print();    G getTranspose(); }; G::G(int m) {    this->m = m;    adj = new list<int> [m]; } void G::DFS(int n, bool visited[]) {    visited[n] = true; // Mark the current node as visited and print it    cout << n << " ";    list<int>::iterator i;    //Recur for all the vertices adjacent to this vertex    for (i = adj[n].begin(); i != adj[n].end(); ++i)       if (!visited[*i])          DFS(*i, visited); } G G::getTranspose() {    G g(m);    for (int n = 0; n< m; n++) {       list<int>::iterator i;       for (i = adj[n].begin(); i != adj[n].end(); ++i) {          g.adj[*i].push_back(n);       }    }    return g; } void G::addEd(int v, int w) {    adj[v].push_back(w); //add w to v's list } void G::fillOrder(int v, bool visited[], stack<int> &Stack) {    visited[v] = true; //Mark the current node as visited and print it    list<int>::iterator i;    //Recur for all the vertices adjacent to this vertex    for (i = adj[v].begin(); i != adj[v].end(); ++i)       if (!visited[*i])          fillOrder(*i, visited, Stack);    Stack.push(v); } int G::print() { //print the solution    stack<int> Stack;    bool *visited = new bool[m];    for (int i = 0; i < m; i++)       visited[i] = false;    for (int i = 0; i < m; i++)       if (visited[i] == false)          fillOrder(i, visited, Stack);    G graph= getTranspose(); //Create a reversed graph    for (int i = 0; i < m; i++)//Mark all the vertices as not visited       visited[i] = false;    int count = 0;    //now process all vertices in order defined by Stack    while (Stack.empty() == false) {       int v = Stack.top();       Stack.pop(); //pop vertex from stack       if (visited[v] == false) {          graph.DFS(v, visited);          cout << endl;       }       count++;    }    return count; } int main() {    G g(5);    g.addEd(2, 1);    g.addEd(3, 2);    g.addEd(1, 0);    g.addEd(0, 3);    g.addEd(3, 1);    cout << "Following are strongly connected components    in given graph \n";    if (g.print() > 1) {       cout << "Graph is weakly connected.";    } else {       cout << "Graph is strongly connected.";    }    return 0; }

Output

Following are strongly connected components in given graph 4 0 1 2 3 Graph is weakly connected.