Kosaraju's Algorithm
Strongly Connected Components & Bridges DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Number of Strongly Connected Components in a Directed Graph (Kosaraju's Algorithm), Directed Graph, Graph Traversal, Depth-First Search, Strongly Connected Components, Stack, Adjacency List, Time Complexity, Space Complexity, Connected Components, complexity analysis, graph algorithms, kosaraju’s algorithm, dfs, stack, graph properties, Strongly Connected Components (Kosaraju's).
Problem: Find the Number of Strongly Connected Components Problem Statement Given a Directed Graph with V vertices (Numbered from 0 to V 1) and E edges, find the number of strongly connected components in the graph. A component is called a Strongly Connected Component (SCC) if for every possible pair of vertices (u, v) inside that component, u is reachable from v and v is reachable from u. Input Specification The first line contains two integers V and E, representing the number of vertices and edges, respectively. The next E lines each contain two integers, u and v, denoting a directed edge from vertex u to vertex v. Output Specification Output a single integer, the number of strongly connected components in the given graph. Constraints 1 <= V <= 10^5 0 <= E <= 2 10^5 0 <= u, v < V Sample Test Cases Sample Input 1: Sample Output 1: Explanation 1: Three strongly connected components are: (0,1,2), (3), (4). Sample Input 2: Sample Output 2: Explanation 2: Four strongly connected components are: (0,1,2), (3,4,5), (6,7), (single vertex components like (3) are always SCCs).