| Show all threads Hide all threads Show all messages Hide all messages |
| Hint | coolboy19521 | 1272. Non-Yekaterinburg Subway | 7 Aug 2024 13:23 | 1 |
Hint coolboy19521 7 Aug 2024 13:23 It ain't a problem to include all the tunnels because apparently they have no cost. So include all of them and then count the number of connected components (let's call it l). The answer is not dependent to the bridges. It is just l-1. |
| for the WA14 boys | Grandmaster | 1272. Non-Yekaterinburg Subway | 4 Apr 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. Non-Yekaterinburg Subway | 4 Nov 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. Non-Yekaterinburg Subway | 16 Jan 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. Non-Yekaterinburg Subway | 30 Oct 2019 13:46 | 2 |
You can use Disjoint-set data structure. Too complicated for such an easy problem |
| WA #5 | redenventeria | 1272. Non-Yekaterinburg Subway | 30 Oct 2019 13:45 | 3 |
WA #5 redenventeria 6 Jul 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. Non-Yekaterinburg Subway | 30 Oct 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. Non-Yekaterinburg Subway | 30 Oct 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. Non-Yekaterinburg Subway | 3 Mar 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. Non-Yekaterinburg Subway | 11 Jul 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. Non-Yekaterinburg Subway | 2 May 2011 18:38 | 2 |
Hint (+) Roman Lipovsky 26 Oct 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. Non-Yekaterinburg Subway | 23 Apr 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. Non-Yekaterinburg Subway | 22 Jul 2010 00:00 | 3 |
Method SerailHydra 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. 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. Non-Yekaterinburg Subway | 12 Jun 2010 14:17 | 2 |
|
| I think, my algo is correct, but I still wa2 | Roma Labish[Lviv NU] | 1272. Non-Yekaterinburg Subway | 11 Mar 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. Non-Yekaterinburg Subway | 5 May 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 |
