Number of Connected Components
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