New update is available. Click here to update.

Count Strongly Connected Components (Kosaraju’s Algorithm)

HARD

40 mins

24 upvotes

Graph

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

Count Strongly Connected Components (Kosaraju’s Algorithm)

Contributed by

Vishal Modani

Hard

0/120

Avg time to solve 40 mins

Success Rate 65 %

24 upvotes

Problem Statement

You are given an unweighted directed graph having 'V' vertices and 'E' edges. Your task is to count the number of strongly connected components (SCCs) present in the graph.

A directed graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly connected components of a graph are the subgraphs which are themselves strongly connected.

Note :

Use zero-based indexing for the vertices.

The given graph doesn’t contain any self-loops.

Detailed explanation ( Input/output format, Notes, Constraints, Images )

Input Format :

The very first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of every test case contains two space-separated integers ‘V’ and ‘E’ denoting the number of vertices and the number of edges present in the graph. 

The next ‘E’ lines contain two space-separated integers ‘a’ and ‘b’ denoting a directed edge from vertex ‘a’ to ‘b’.

Output Format :

For each test case, return an integer denoting the number of strongly connected components (SCCs) present in the graph.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= V <= 10^4
0 <= E <= 10^4
0 <= a, b < V

Time Limit: 1 sec

Sample Input 1 :

Sample Output 1 :

Explanation of sample input 1 :

For the first test case, the graph is shown below. There are two SCCs in the graph, which are enclosed in the boxes as shown in the image below.

Sample Input 2 :

Sample Output 2 :

1
2

Auto

Console