EC_MUN - The world and Contients
Aplemon is a very active boy and now plans to travel around the world, but before that he remembered we had five continents, now he thinks it's not true, he wants everyone to live happily, so he thinks to unite all of the world into one great continent.
Given the description of the countries and their connections with other countries, we say that a continent is a set of countries that are connected together (being possible to travel to any other country on the same continent), forming the continents. Now Aplemon wants to build large bridges to link these continents, he wants to know what is the minimum number of bridges needed to connect all the continents and the world is happy. Help him to answer the question.
Input
The first line contains an integer N (1 <= N <= 100000) the number of countries and M (1 <= M <= 100000) that represents the number of connections in the world.
Output
Print the minimum amount of bridges Aplemon must build for the world to be happy.
Example
Input: 5 3 1 2 2 3 4 5 Output: 1
hide comments
Ehor Nechiporenko:
2014-09-16 08:25:21
Please move this problem to tutorial list, it's trivial. And there are already a lot of problems with the similar conditions in SPOJ |
|
wisfaq:
2014-09-16 08:25:21
Please remove unnecessary language restrictions. |
Added by: | Eddy Cael |
Date: | 2014-08-31 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | C C++ 4.3.2 CPP JAVA |
Resource: | Internas UTO 2014 |