Discussion @ 1272. Non-Yekaterinburg Subway @ Timus Online Judge

I think, my algo is correct, but I still wa2 Roma Labish[Lviv NU] 11 Feb 2007 22:13

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

Re: I think, my algo is correct, but I still wa2 diver[rus] 13 Feb 2007 20:46

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

Re: I think, my algo is correct, but I still wa2 Roma Labish[Lviv NU] 5 Mar 2007 01:03

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?

Re: I think, my algo is correct, but I still wa2 DixonD (Lviv NU) 10 Mar 2007 01:40

In your case, 'wrang' is wrong :)

Re: I think, my algo is correct, but I still wa2 Romko [Lviv NU] 10 Mar 2007 01:44

Re: I think, my algo is correct, but I still wa2 diver[rus] 10 Mar 2007 02:03

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.

Re: I think, my algo is correct, but I still wa2 Romko [Lviv NU] 10 Mar 2007 02:13

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

Re: I think, my algo is correct, but I still wa2 Romko [Lviv NU] 11 Mar 2007 19:07

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

Discussion of Problem 1272. Non-Yekaterinburg Subway