| ENG RUS | Timus Online Judge |
Discussion of Problem 1272. Non-Yekaterinburg SubwayGrandmaster for the WA14 boys // Problem 1272. Non-Yekaterinburg Subway 4 Apr 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 :) // Problem 1272. Non-Yekaterinburg Subway 4 Nov 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] // Problem 1272. Non-Yekaterinburg Subway 11 Aug 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 // Problem 1272. Non-Yekaterinburg Subway 16 Jan 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] // Problem 1272. Non-Yekaterinburg Subway 16 Jan 2017 23:56 You can use Disjoint-set data structure. ____NOOR Re: Easy problem // Problem 1272. Non-Yekaterinburg Subway 30 Oct 2019 13:46 Too complicated for such an easy problem redenventeria WA #5 [2] // Problem 1272. Non-Yekaterinburg Subway 6 Jul 2017 00:21 Please, help. Mahilewets Re: WA #5 // Problem 1272. Non-Yekaterinburg Subway 6 Jul 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 // Problem 1272. Non-Yekaterinburg Subway 30 Oct 2019 13:45 You have to give us more information Luka Bulatovic Solved(MST) [4] // Problem 1272. Non-Yekaterinburg Subway 21 Aug 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] // Problem 1272. Non-Yekaterinburg Subway 20 Dec 2013 14:08 The problem is much easier. You don't need to use Kruskal or Prim to solve it. adamant Re: Solved(MST) // Problem 1272. Non-Yekaterinburg Subway 22 Dec 2013 00:47 Well, yes, but we can use this problem to train skills of writing MST algo =) davidlescano Re: Solved(MST) // Problem 1272. Non-Yekaterinburg Subway 8 Jul 2017 21:32 DFS! ____NOOR Re: Solved(MST) // Problem 1272. Non-Yekaterinburg Subway 30 Oct 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] // Problem 1272. Non-Yekaterinburg Subway 24 Jun 2019 09:33 Used bfs instead dfs ____NOOR Re: Runtime Error #12 on Python3 // Problem 1272. Non-Yekaterinburg Subway 30 Oct 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 // Problem 1272. Non-Yekaterinburg Subway 3 Mar 2016 00:13 try this test: 1 0 0 answer: 0 Hrayr[Goris N4 High School] If you want to do this fast. // Problem 1272. Non-Yekaterinburg Subway 11 Jul 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] // Problem 1272. Non-Yekaterinburg Subway 26 Oct 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 (+) // Problem 1272. Non-Yekaterinburg Subway 2 May 2011 18:38 I think? it is clear =) Elday WA#1, WTF??? // Problem 1272. Non-Yekaterinburg Subway 23 Apr 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] // Problem 1272. Non-Yekaterinburg Subway 10 Nov 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 // Problem 1272. Non-Yekaterinburg Subway 6 Apr 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 // Problem 1272. Non-Yekaterinburg Subway 22 Jul 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] // Problem 1272. Non-Yekaterinburg Subway 19 Aug 2006 18:40 Use Union-find set... {SESC USU} Averin Artyom Re: The O(n) algorithm // Problem 1272. Non-Yekaterinburg Subway 12 Jun 2010 14:17 Or just DFS. 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 :p 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!!! KAV Am I right or I misunderstand the problem? [3] // Problem 1272. Non-Yekaterinburg Subway 25 Mar 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] // Problem 1272. Non-Yekaterinburg Subway 4 May 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] // Problem 1272. Non-Yekaterinburg Subway 5 May 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? // Problem 1272. Non-Yekaterinburg Subway 5 May 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
|