All problems

Number of Connected Components

hardPythonGraphsUnion-Find

Loxley Telecom is auditing a site network. Each cable joins two routers and carries traffic both ways, so two cabled routers are in the same network, and so is anything either of them reaches. A router with no cable at all is still a network — a network of one, which is exactly what the audit is looking for.

Task: Print how many separate networks the routers form.

Input

The first line holds two integers separated by a space: n, the number of routers labelled 0 to n-1, and m, the number of cables. Each of the next m lines holds two integers u v, a cable joining router u and router v. m may be 0. The same pair may be cabled more than once.

Output

One line holding a single integer: the number of separate networks. Two routers are in the same network when some run of cables leads from one to the other, in either direction. A router with no cables counts as a network on its own.

Example:

Input:
5 3
0 1
1 2
3 4

Output:
2

(components: {0,1,2} and {3,4})

Sign in to solve this problem

Reading problems is free for everyone — solving them (Run, Submit, and tracking what you've solved) needs an account.

Sign in

Discussion

Sign in to join the discussion — reading is open to everyone.

Loading comments…