A farm has n irrigation zones numbered 1 through n. Some pairs of zones are joined by a bidirectional water pipe. Two zones belong to the same cluster if water can travel between them through one or more pipes. A zone with no pipes forms a cluster by itself.
Report how many clusters there are.
Line 1: two integers n and m, the number of zones and the number of pipes.
Next m lines: two integers u and v each, meaning a pipe joins zone u and zone v. A pipe may be listed more than once; a pipe never joins a zone to itself.
A single integer: the number of clusters.
Example 1
Input
4 2 1 2 3 4
Expected
2
Explanation
Zones 1 and 2 share a pipe (one cluster); zones 3 and 4 share a pipe (another cluster). That is 2 clusters.
Example 2
Input
3 0
Expected
3
Explanation
There are no pipes, so each of the 3 zones stands alone: 3 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 →