Total Strongly Connected Components - Solution

Problem : Total Strongly Connected Components

You are given a graph G with V vertices and E edges. You need to find total number of strongly connected components.

Note: A strongly connected component (SCC) of a directed graph is a maximal strongly connected subgraph.
Total Strongly Connected Components Contest Problem

Hint

Input:
The first line of input contains T denoting the number of testcases. T testcases follow. Each testcase contains 2 lines of input. The first line contains V and E. The second line contains E pairs of vertices, i.e start node and end node for an edge.

Output:
For each testcase, in a new line, print the total strongle connected components.

Constraints:
1 <= T <= 100
1 <= E, V <= 100

Examples:
Input:
1
5 5
1 0 0 2 2 1 0 3 3 4
Output:
3
Explanation:
Testcase1: The graph and components are as follows:

[Solved] Total Strongly Connected Components Contest Problem

Solution:

 #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
    void 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;

    // 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
    Stack.push(v);
}

// The main function that finds and prints all strongly connected
// components
void Graph::printSCCs()
{
    
    int counter=0;
    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;

    // 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)
        {
            counter++;
            gr.DFSUtil(v, visited);
        
        }
    }
    
    cout<<counter<<endl;
}

// Driver program to test above functions
int main()
{
    int testcases;
    cin>>testcases;
    
    while(testcases--)
    {
        int V, E;
        cin>>V>>E;
        Graph g(V);
        for(int i=0;i<E;i++)
        {
            int u,v;
            cin>>u>>v;
            g.addEdge(u,v);
        }
        
        g.printSCCs();
       
    }
    

    return 0;
}