[Solved] Total Strongly Connected Components Contest 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

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:

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; 
} 

import java.util.*;
import java.io.*;
import java.lang.*;

public class Kosaraju
{
   public void DFS(List<Integer>[] graph, int v, boolean[] visited, List<Integer> comp) 
    {
        visited[v] = true;
        for (int i = 0; i < graph[v].size(); i++)

            if (!visited[graph[v].get(i)])
                DFS(graph, graph[v].get(i), visited, comp);

        comp.add(v);
    }

   public List<Integer> fillOrder(List<Integer>[] graph, boolean[] visited) 
    {        

        int V = graph.length;
        List<Integer> order = new ArrayList<Integer>();
        for (int i = 0; i < V; i++)

            if (!visited[i])DFS(graph, i, visited, order);

        return order;
    }

   @SuppressWarnings("unchecked")
    public List<Integer>[] getTranspose(List<Integer>[] graph)
    {

        int V = graph.length;
        List<Integer>[] g = new List[V];
        for (int i = 0; i < V; i++)
            g[i] = new ArrayList<Integer>();
        for (int v = 0; v < V; v++)
            for (int i = 0; i < graph[v].size(); i++)
                g[graph[v].get(i)].add(v);

        return g;}

    public List<List<Integer>> getSCComponents(List<Integer>[] graph)
    {
        int V = graph.length;
        boolean[] visited = new boolean[V];
        List<Integer> order = fillOrder(graph, visited);       
        List<Integer>[] reverseGraph = getTranspose(graph);        
        visited = new boolean[V];
        Collections.reverse(order);
        List<List<Integer>> SCComp = new ArrayList<>();
        for (int i = 0; i < order.size(); i++)
        {
            int v = order.get(i);
            if (!visited[v]) 
            {
                List<Integer> comp = new ArrayList<>();
                DFS(reverseGraph, v, visited, comp);
                SCComp.add(comp);
            }
        }
    return SCComp;
    }
    @SuppressWarnings("unchecked")
    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);
        int t = scan.nextInt();
        while(t-- > 0)
        {
            Kosaraju k = new Kosaraju();

        int V = scan.nextInt();
        int E = scan.nextInt();
        List<Integer>[] g = new List[V];
        for (int i = 0; i < V; i++)
            g[i] = new ArrayList<Integer>();
        for (int i = 0; i < E; i++)
        {
            int x = scan.nextInt();
            int y = scan.nextInt();
            g[x].add(y);
        }
        List<List<Integer>> scComponents = k.getSCComponents(g);
        System.out.println(scComponents.size());    
       }
     }    
}

Happy Learning – If you require any further information, feel free to contact me.