Connected Components

easyPROGraphs & TraversalNetflix DSA

Given n nodes (0-indexed) and a list of undirected edges, return the number of connected components in the graph.

Implement count_components(n, edges), where n is the number of nodes and edges is a list of [a, b] pairs (empty if there are no edges). Return the count as an integer.

In the example below, the first line is n and the second line lists the edges as a,b pairs separated by semicolons.

Example

Input

5
0,1;1,2;3,4

Output

Reasoning

n = 5 means the graph has nodes $0, 1, 2, 3, 4$ . The sample edges are the pairs $(0,1)$ , $(1,2)$ and $(3,4)$ ; each edge is undirected, so it can be walked in either direction.
A connected component is a largest possible group of nodes in which every node can reach every other by following edges. Reachability chains: $0$ has no direct edge to $2$ , but $0 \to 1 \to 2$ links them, so $\{0, 1, 2\}$ is one group.
Nodes $3$ and $4$ share an edge, giving the group $\{3, 4\}$ . No edge touches both groups, so neither can grow further.
Every node lands in exactly one group, and there are $2$ groups, so the output is 2.
Notice that only connectivity matters, not how many edges there are: adding an edge $(0,2)$ would leave the answer at 2, while a single edge $(2,3)$ would merge everything into 1. A node with no edges at all still counts as its own component, so n = 3 with no edges gives 3.

Constraints

1 <= n <= 2000
0 <= edges <= 5000

Learn this in

GraphsDSA Study Plan

More from Netflix DSA

Search a 2D Matrixeasy Merge Intervalsmedium Sort Colorsmedium Kth Largest Element in an Arraymedium Missing Numbereasy

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test results