Lets graph G has n vertices and k components => number of m edges meet the conditions:
n-k <= m <= 1/2(n-k)(n-k+1).
Therefor k >= n-m. So, min(k) = n-m.
We have number of islands = N, and number of tunnels K. Why the answer isn't N-K-1 ?

Edited by author 11.02.2007 22:13

Try this test
4 5 0
1 2
1 3
1 4
2 3
3 4
Answer 0, your answer 4 - 5 - 1 = 2
or this
5 4 1
1 2
3 4
4 5
3 5
2 3
Answer 1, your answer 5 - 4 - 1 = 0

Why for the second test answer is 1? There is only one component, so you shouldn't to add any edges. And one more thing, if n < k answer is 0. So what's wrang?

In your case, 'wrang' is wrong :)

:p

5 4 1
1 2
3 4
4 5
3 5
2 3

Count of tunnels is 4. So graph with edges 1 2, 3 4, 4 5, 3 5 have 2 components. You should use exactly one bridge (edge 2 3) to make it connected.
Read problem statement more carefully.
Task is to delete maximal number of "bridges" in given graph.

Ok! Thank. I'll try to find another way to solve it.

I had done it:) Thanks to all for help!!!