Connected Components Logic
Introduction to Graphs DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Connected Components in an Undirected Graph and Graph Traversal Approaches, Graph, Undirected Graph, Edge, Adjacency List, Graph Traversal, Depth-First Search, Breadth-First Search, Time Complexity, Space Complexity, Arrays, Recursion, Queue, visited tracking, graph components, graph traversal, graph properties, graph theory, Connected Components, Graph Traversal Utilities.
Number of Connected Components Problem Statement Given an undirected graph with N nodes and M edges, determine the total number of connected components in the graph. A connected component of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph. Input Specification The first line contains two integers N and M, representing the number of nodes and the number of edges, respectively. The next M lines each contain two integers u and v, denoting an undirected edge between node u and node v. Nodes are 1 indexed. Output Specification Output a single integer, the total number of connected components in the graph. Constraints 1 <= N <= 10^5 0 <= M <= 10^5 1 <= u, v <= N No self loops or multiple edges between the same pair of nodes. Sample Test Case Input Output Explanation The graph has nodes 1 to 10 and 8 edges. The connected components are: 1. {1, 2, 3, 4} 2. {5, 6, 7} 3. {8, 9} 4. {10} (Node 10 is isolated and forms its own component)