Loading...
Loading...
Loading...
A hostel has n rooms, numbered 1 to n, linked by cables in both directions. The network was built with exactly n − 1 cables, so every room was connected and there were no loops.
Later, one extra cable was added between two rooms, so now there are n cables and exactly one loop. Find a cable you can remove so that every room is still connected and there is no loop.
Several cables may work. Print the one that appears last in the input.
Example 1
Input
3 3 1 2 1 3 2 3
Output
2 3
All three cables are on the loop. The last one is 2 3.
Example 2
Input
5 5 1 2 2 3 3 4 1 4 1 5
Output
1 4
The loop is 1-2-3-4. Cable 1 5 is not on it, so 1 4 is the last cable that works.
Try the problem first. Open one hint at a time.
Add the cables one at a time in input order. Which cable is the first one that joins two rooms that are already connected?
That cable closes the loop. Every other cable on the loop came earlier, so it is the last loop cable in the input.
To check "already connected" quickly, keep groups of rooms with a parent array and a find method that returns a group's leader.
If both rooms of a cable have the same leader, print that cable. Otherwise merge the two groups by pointing one leader at the other.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor