Bridges

mac2025-02-28  7

Bridges

时间限制 : 1sec / 空间限制: 256MB

题意:

There are n n n cities in a country and some of them are connected by bridges while some are not. For convenience, the government decide to build some bridges so that every city could be reached from other n − 1 n-1 n1 cities using only bridges. Now there are already m m m bridges, please calculate the minimum number of bridges to be built so that the government could spend the least money on building bridges.

输入:

The first line contains two integers n n n and m m m, indicate the number of cities and the number of bridges separately. 1 < = n , m < = 1 0 5 . 1 <= n,m <= 10^5. 1<=n,m<=105.

Followings are m m m lines. Every line contains two integers a i a_i ai and b i b_i bi, means two cities a i a_i ai and b i b_i bi are connected by a bridge. 1 < = a i , b i < = n . 1 <= a_i,b_i<=n. 1<=ai,bi<=n.

Every two integers are separated by a space.

Note that the birdges are bidirectional and it’s possible that a bridge connects the same city and two different cities are connected by multiple bridges.

输出:

One integer, means the minimum number of bridges to be built.

样例一:

输入:

3 2

1 2

2 3

输出:

0

样例二:

###输入:

3 1

1 2

###输出:

1

最新回复(0)