All problems

Number of Connected Components in an Undirected Graph

Medium · graph traversal

A network has n computers, numbered 0 to n - 1. The list edges holds cables between them: each entry [a, b] is a cable that joins computer a and computer b, and works in both directions.

Two computers belong to the same group if you can get from one to the other by following cables, possibly through other computers. A computer with no cables is a group of its own.

Return how many separate groups the network has.

The same cable may be listed more than once, and an entry may join a computer to itself ([a, a]). Neither changes the groups. If edges is empty, every computer is its own group.

Examples

Example 1

Input: n = 5, edges = [[0, 1], [1, 2], [3, 4]]

Output: 2

Computers 0, 1 and 2 are linked together, and so are 3 and 4. Nothing connects the two sets.

Example 2

Input: n = 5, edges = [[0, 1], [1, 2], [2, 3], [3, 4]]

Output: 1

The cables form one long chain, so every computer can reach every other.

Example 3

Input: n = 4, edges = []

Output: 4

With no cables, each computer is alone.

Constraints