| Submit | All submissions | Best solutions | Back to list |
SUBMERGE - Submerging Islands |
Vice City is built over a group of islands, with bridges connecting them. As anyone in Vice City knows, the biggest fear of vice-citiers is that some day the islands will submerge. The big problem with this is that once the islands submerge, some of the other islands could get disconnected. You have been hired by the mayor of Vice city to tell him how many islands, when submerged, will disconnect parts of Vice City. You should know that initially all the islands of the city are connected.
Input
The input will consist of a series of test cases. Each test case will start with the number N (1 ≤ N ≤ 10^4) of islands, and the number M of bridges (1 ≤ M ≤ 10^5). Following there will be M lines each describing a bridge. Each of these M lines will contain two integers Ui, Vi (1 ≤ Ui,Vi ≤ N), indicating that there is a bridge connecting islands Ui and Vi. The input ends with a case where N = M = 0.
Output
For each case on the input you must print a line indicating the number of islands that, when submerged, will disconnect parts of the city.
Example
Input: 3 3 1 2 2 3 1 3 6 8 1 3 6 1 6 3 4 1 6 4 5 2 3 2 3 5 0 0 Output: 0 1
| Added by: | Hector Navarro |
| Date: | 2013-05-16 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
| Resource: | MiniMaraton 2013 - UCV |
hide comments
|
|||||||||
|
2020-08-11 11:39:48
hints:-> store cut vertex in a set(which will return you unique cut vertex) |
|||||||||
|
2020-07-08 15:42:55
Brain: write it. me : nooo. Brain: do it. Me : AC in just one GO goa Gone, |
|||||||||
|
2020-06-08 17:43:04
AC in one go!!! easy peasy.. :) |
|||||||||
|
2020-05-28 03:33:42
Ac in one Go.There we go!!!!! |
|||||||||
|
2020-04-24 18:30:38
AC in one go :0 |
|||||||||
|
2020-04-21 10:25:29
AC in one Go!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! |
|||||||||
|
2020-03-02 21:52:51
Use bool [] or a set to store articulation points...instead of incrementing a variable coz 5 5 1 2 2 3 3 1 3 4 3 5 0 0 fails Correct :1 U''ll get :2 |
|||||||||
|
2020-02-22 13:56:17
@amstan use set instead of boolean array. Last edit: 2020-02-22 13:56:46 |
|||||||||
|
2019-12-22 15:18:23
The test cases are a bit weak. I didn't check if the root is an articulation point and my code still passed. 3 2 1 2 1 3 0 0 |
|||||||||
|
2019-07-01 07:12:49
It's a simple articulation point problem but my code was failing on this test-case: 5 5 1 2 2 3 3 1 3 4 3 5 0 0 Correct Output : 1 My Output : 2 How did I correct this ? Use boolean ap[] array to store which vertex is ap |
|||||||||
RSS