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

Roma Labish[Lviv NU] I think, my algo is correct, but I still wa2 [7] // Problem 1272. Non-Yekaterinburg Subway 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

diver[rus] Re: I think, my algo is correct, but I still wa2 [6] // Problem 1272. Non-Yekaterinburg Subway 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

Roma Labish[Lviv NU] Re: I think, my algo is correct, but I still wa2 [5] // Problem 1272. Non-Yekaterinburg Subway 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?

DixonD (Lviv NU) Re: I think, my algo is correct, but I still wa2 [1] // Problem 1272. Non-Yekaterinburg Subway 10 Mar 2007 01:40

In your case, 'wrang' is wrong :)

Romko [Lviv NU] Re: I think, my algo is correct, but I still wa2 // Problem 1272. Non-Yekaterinburg Subway 10 Mar 2007 01:44

diver[rus] Re: I think, my algo is correct, but I still wa2 [2] // Problem 1272. Non-Yekaterinburg Subway 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.

Romko [Lviv NU] Re: I think, my algo is correct, but I still wa2 [1] // Problem 1272. Non-Yekaterinburg Subway 10 Mar 2007 02:13

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

Romko [Lviv NU] Re: I think, my algo is correct, but I still wa2 // Problem 1272. Non-Yekaterinburg Subway 11 Mar 2007 19:07

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

Discussion of Problem 1272. Non-Yekaterinburg Subway