| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
| for the WA14 boys | Grandmaster | 1272. Метро не в Екатеринбурге | 4 апр 2022 15:11 | 1 |
4 3 2
1 2
2 3
2 4
3 4
1 4
correct answer is 0. |
| Ready algorithm and all tests for lazy boys :) | D4nick | 1272. Метро не в Екатеринбурге | 4 ноя 2020 21:19 | 1 |
http://e-maxx.ru/algo/connected_componentsYou need to output number of components minus 1. Tests: 4 4 0 3 4 1 2 3 1 2 4 0 1 0 0 0 6 0 0 5 6 5 1 1 2 1 4 2 5 3 6 4 5 1 2 1 6 5 0 1 2 1 4 2 5 3 6 4 5 1 6 3 4 1 2 2 3 4 5 2 6 4 0 1 3 3 4 4 6 5 6 1 Edited by author 04.11.2020 21:20 |
| If you have WA #14 | Insectophob | 1272. Метро не в Екатеринбурге | 16 янв 2020 17:10 | 2 |
I hope these tests will be useful for you :)
4 5 0
3 4
1 2
3 1
2 4
and
7 7 0
1 2
1 3
2 4
2 5
3 6
3 7
4 7
The output must be 0 in both cases, but if you've done something wrong, it can be -1. Make sure your determination of connected components isn't wrong. you gave the wrong 1 test
here's the correct
4 4 0
3 4
1 2
3 1
2 4
answer : 0 |
| Easy problem | Maksimus El Diablo | 1272. Метро не в Екатеринбурге | 30 окт 2019 13:46 | 2 |
You can use Disjoint-set data structure. Too complicated for such an easy problem |
| WA #5 | redenventeria | 1272. Метро не в Екатеринбурге | 30 окт 2019 13:45 | 3 |
WA #5 redenventeria 6 июл 2017 00:21 I can't help you without details of your algorithm.
I have never encountered WA#5.
I have some Stack-Overflow's because of critical mistake in my find_set function for Disjoint Set Union.
After fixing AC.
Edited by author 06.07.2017 09:50 You have to give us more information |
| Solved(MST) | Luka Bulatovic | 1272. Метро не в Екатеринбурге | 30 окт 2019 13:43 | 5 |
Solution is Minimum spanning tree (Kruskal or Prim Algorithm). Put low cost on tunnels, and much higher one on bridges with using priority queue ;) The problem is much easier. You don't need to use Kruskal or Prim to solve it. Well, yes, but we can use this problem to train skills of writing MST algo =) You are trying to kill a fly with a nuclear Bomb :)
Edited by author 30.10.2019 13:44 |
| Runtime Error #12 on Python3 | Tihon Molotkov`~ | 1272. Метро не в Екатеринбурге | 30 окт 2019 13:40 | 2 |
It does not matter. Both DFS and BFS can be used to solve the problem. Yet, DFS code is shorter and nicer that BFS code. So, DFS is a better choice. So, I used DFS instead of BFS
Edited by author 30.10.2019 13:41
Edited by author 30.10.2019 13:41 |
| if you have WA #4 | Sergey Ubogov | 1272. Метро не в Екатеринбурге | 3 мар 2016 00:13 | 1 |
try this test:
1 0 0
answer:
0 |
| If you want to do this fast. | Hrayr[Goris N4 High School] | 1272. Метро не в Екатеринбурге | 11 июл 2011 23:16 | 1 |
I think counting total amount of graph components and then printing it-1 faster than to do it by MST.We can do it in O(n+k) time and we needn't know anything about bridges.
Edited by author 11.07.2011 23:20 |
| Hint (+) | Roman Lipovsky | 1272. Метро не в Екатеринбурге | 2 май 2011 18:38 | 2 |
Hint (+) Roman Lipovsky 26 окт 2004 17:11 No need to read information about bridges!
Just count number of connected components in graph and
write (number-1). |
| WA#1, WTF??? | Elday | 1272. Метро не в Екатеринбурге | 23 апр 2011 19:27 | 1 |
I have right answer on the test on task page.
I have right answers on all testcases that i found in this forum.
There is a stupid error in my code. Where?
[here was a code]
answer: forgot initialize all parametres in constructor. AC now :)
Edited by author 23.04.2011 20:00 |
| Method | SerailHydra | 1272. Метро не в Екатеринбурге | 22 июл 2010 00:00 | 3 |
Method SerailHydra 10 ноя 2007 17:57 You can consider that the cost of the tunnel is 1, and the bridge is 24000. Then it becomes a MST problem. would be better to make weight tunnel 0, the weight of the bridge 1, and the answer is weight of minimal spanning tree Your idea is interesting, but weird a bit. :)
It can be solved with DFS easily. Moreover, you even don't need to know anything about bridges. |
| The O(n) algorithm | wangyin | 1272. Метро не в Екатеринбурге | 12 июн 2010 14:17 | 2 |
|
| I think, my algo is correct, but I still wa2 | Roma Labish[Lviv NU] | 1272. Метро не в Екатеринбурге | 11 мар 2007 19:07 | 8 |
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 :) 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!!! |
| Am I right or I misunderstand the problem? | KAV | 1272. Метро не в Екатеринбурге | 5 май 2006 17:21 | 4 |
Information about bridges is extra, isn't it? It isn't necessary to read it, as graph tonnels+bridges is connected. It's need to count the number of components of the graph and the answer is number-1.
Is this all true???
Because using this algo I always have WA 14 :( So do I! Please, someone tell me what's the test 14?
Edited by author 04.05.2006 22:49 I haven't overcome this problem yet :(. AlexF, do you think that our idea is wrong? Yes!!! I got AC!! Our idea is right! )) I found the test which my program coudn't pass. Here it is:
9 3 6
6 8
5 8
2 1
1 3
2 3
3 4
7 4
9 4
8 9
Right answer is 5.
If You want, KAV, you can give me your mail and I'll send to you my solution. ;)
Edited by author 05.05.2006 17:21
Edited by author 05.05.2006 18:10
Edited by author 05.05.2006 18:10 |
