| ENG RUS | Timus Online Judge |
Обсуждение задачи 1272. Метро не в ЕкатеринбургеGrandmaster for the WA14 boys // Задача 1272. Метро не в Екатеринбурге 4 апр 2022 15:11 4 3 2 1 2 2 3 2 4 3 4 1 4 correct answer is 0. D4nick Ready algorithm and all tests for lazy boys :) // Задача 1272. Метро не в Екатеринбурге 4 ноя 2020 21:19 http://e-maxx.ru/algo/connected_components You 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 Insectophob If you have WA #14 [1] // Задача 1272. Метро не в Екатеринбурге 11 авг 2014 01:51 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. mecing Re: If you have WA #14 // Задача 1272. Метро не в Екатеринбурге 16 янв 2020 17:10 you gave the wrong 1 test here's the correct 4 4 0 3 4 1 2 3 1 2 4 answer : 0 Maksimus El Diablo Easy problem [1] // Задача 1272. Метро не в Екатеринбурге 16 янв 2017 23:56 You can use Disjoint-set data structure. ____NOOR Re: Easy problem // Задача 1272. Метро не в Екатеринбурге 30 окт 2019 13:46 Too complicated for such an easy problem redenventeria WA #5 [2] // Задача 1272. Метро не в Екатеринбурге 6 июл 2017 00:21 Please, help. Mahilewets Re: WA #5 // Задача 1272. Метро не в Екатеринбурге 6 июл 2017 09:49 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 ____NOOR Re: WA #5 // Задача 1272. Метро не в Екатеринбурге 30 окт 2019 13:45 You have to give us more information Luka Bulatovic Solved(MST) [4] // Задача 1272. Метро не в Екатеринбурге 21 авг 2011 14:00 Solution is Minimum spanning tree (Kruskal or Prim Algorithm). Put low cost on tunnels, and much higher one on bridges with using priority queue ;) mikroz Re: Solved(MST) [1] // Задача 1272. Метро не в Екатеринбурге 20 дек 2013 14:08 The problem is much easier. You don't need to use Kruskal or Prim to solve it. adamant Re: Solved(MST) // Задача 1272. Метро не в Екатеринбурге 22 дек 2013 00:47 Well, yes, but we can use this problem to train skills of writing MST algo =) davidlescano Re: Solved(MST) // Задача 1272. Метро не в Екатеринбурге 8 июл 2017 21:32 DFS! ____NOOR Re: Solved(MST) // Задача 1272. Метро не в Екатеринбурге 30 окт 2019 13:43 You are trying to kill a fly with a nuclear Bomb :) Edited by author 30.10.2019 13:44 Tihon Molotkov`~ Runtime Error #12 on Python3 [1] // Задача 1272. Метро не в Екатеринбурге 24 июн 2019 09:33 Used bfs instead dfs ____NOOR Re: Runtime Error #12 on Python3 // Задача 1272. Метро не в Екатеринбурге 30 окт 2019 13:40 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 Sergey Ubogov if you have WA #4 // Задача 1272. Метро не в Екатеринбурге 3 мар 2016 00:13 try this test: 1 0 0 answer: 0 Hrayr[Goris N4 High School] If you want to do this fast. // Задача 1272. Метро не в Екатеринбурге 11 июл 2011 23:16 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 Roman Lipovsky Hint (+) [1] // Задача 1272. Метро не в Екатеринбурге 26 окт 2004 17:11 No need to read information about bridges! Just count number of connected components in graph and write (number-1). Edgar Rokyan Re: Hint (+) // Задача 1272. Метро не в Екатеринбурге 2 май 2011 18:38 I think? it is clear =) Elday WA#1, WTF??? // Задача 1272. Метро не в Екатеринбурге 23 апр 2011 19:27 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 SerailHydra Method [2] // Задача 1272. Метро не в Екатеринбурге 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. Erop [USU] Re: Method // Задача 1272. Метро не в Екатеринбурге 6 апр 2010 20:22 would be better to make weight tunnel 0, the weight of the bridge 1, and the answer is weight of minimal spanning tree Artem Khizha [DNU] Re: Method // Задача 1272. Метро не в Екатеринбурге 22 июл 2010 00:00 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. wangyin The O(n) algorithm [1] // Задача 1272. Метро не в Екатеринбурге 19 авг 2006 18:40 Use Union-find set... {SESC USU} Averin Artyom Re: The O(n) algorithm // Задача 1272. Метро не в Екатеринбурге 12 июн 2010 14:17 Or just DFS. Roma Labish[Lviv NU] I think, my algo is correct, but I still wa2 [7] // Задача 1272. Метро не в Екатеринбурге 11 фев 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] // Задача 1272. Метро не в Екатеринбурге 13 фев 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] // Задача 1272. Метро не в Екатеринбурге 5 мар 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] // Задача 1272. Метро не в Екатеринбурге 10 мар 2007 01:40 In your case, 'wrang' is wrong :) Romko [Lviv NU] Re: I think, my algo is correct, but I still wa2 // Задача 1272. Метро не в Екатеринбурге 10 мар 2007 01:44 :p diver[rus] Re: I think, my algo is correct, but I still wa2 [2] // Задача 1272. Метро не в Екатеринбурге 10 мар 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] // Задача 1272. Метро не в Екатеринбурге 10 мар 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 // Задача 1272. Метро не в Екатеринбурге 11 мар 2007 19:07 I had done it:) Thanks to all for help!!! KAV Am I right or I misunderstand the problem? [3] // Задача 1272. Метро не в Екатеринбурге 25 мар 2006 20:49 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 :( AlexF Re: Am I right or I misunderstand the problem? [2] // Задача 1272. Метро не в Екатеринбурге 4 май 2006 22:48 So do I! Please, someone tell me what's the test 14? Edited by author 04.05.2006 22:49 KAV Re: Am I right or I misunderstand the problem? [1] // Задача 1272. Метро не в Екатеринбурге 5 май 2006 08:07 I haven't overcome this problem yet :(. AlexF, do you think that our idea is wrong? AlexF Re: Am I right or I misunderstand the problem? // Задача 1272. Метро не в Екатеринбурге 5 май 2006 17:21 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
|