Loading...
Loading...
Loading...
A hostel has n Wi-Fi routers, numbered 1 to n, joined by m cables. A cable works in both directions. Two routers can talk if there is a path of cables between them, maybe through other routers. The network may already be in several separate pieces.
A cable is critical if cutting only that cable stops some pair of routers that could talk before from talking now. The warden wants a backup cable next to each critical one.
Print every critical cable as u v with u < v, one per line, sorted by u and then by v. If there is no critical cable, print NONE.
u v with u < v, sorted by u and then by v, or the single word NONE.Example 1
Input
6 7 1 2 2 3 3 1 3 4 4 5 5 6 6 4
Output
3 4
Routers 1, 2, 3 form a loop, and so do 4, 5, 6. Only the cable between 3 and 4 joins the two loops, so cutting it splits them.
Example 2
Input
4 4 1 2 2 3 3 4 4 1
Output
NONE
All four routers sit on one loop. Cutting any single cable leaves another way round.
Try the problem first. Open one hint at a time.
A cable is critical exactly when it is not on any loop. Cutting a cable on a loop leaves the way round the loop.
Do one depth-first search and number the routers in the order you first reach them. For each router, also find the smallest number it can climb back to from below it, using one back cable.
For a search cable from u down to a new router v: if everything below v can only climb back to v or lower in the tree, that cable is critical. In numbers, low[v] > num[u].
When you skip the cable you came in on, skip that one cable by its index, not every cable to the parent router. Start a new search from every router not reached yet.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor