A company models its office network as an undirected graph. Machines are numbered 0 through n-1. Some pairs of machines are directly cabled together. Two machines are in the same cluster if you can travel from one to the other by following cables (directly or through other machines).
Given the machines and the cables, report how many clusters the network forms. A machine with no cables of its own still counts as a cluster of size one.
Line 1: two integers n and m — the number of machines and the number of cables.
Next m lines: two integers u v (0-indexed) meaning there is a cable between machine u and machine v.
The graph is undirected. It may contain self-loops (u == v) and duplicate cables; these never change which machines are connected.
A single integer: the number of connected components (clusters).
Two clusters
Input
5 3 0 1 1 2 3 4
Expected
2
Explanation
Machines {0,1,2} form one cluster and {3,4} form another, so there are 2 clusters.
All isolated
Input
4 0
Expected
4
Explanation
No cables at all, so each of the 4 machines is its own cluster: 4 clusters.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →