The problem
There are n places, numbered 0 to n - 1, and no roads. Roads are built one at a time, in the order of the list. A road (a, b) connects a and b in both directions. Return the position in the list of the first road that closes a loop: a road between two places that could already reach each other. Return -1 if no road does.
first_cycle(4, [(0, 1), (1, 2), (2, 0), (2, 3)]) # 2
first_cycle(4, [(0, 1), (1, 2), (2, 3)]) # -1
A road from a place to itself, (a, a), closes a loop at once. So does a second road between the same two places.
Some tests join long chains. Write find with a loop, or make sure your trees stay short (lessons 2 and 3): a recursive find on a path of 100,000 nodes stops with RecursionError.
Limits
- Up to 200,000 places and 200,000 roads.
Builds on DSUF-5 Applications.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | The example | Not run | |
| 2 | No cycle | Not run | |
| 3 | A road to itself | Not run | |
| 4 | The same road twice | Not run | |
| 5 | Lesson 5's roads | Not run | |
| 6 | Separate groups | Not run | |
| 7 | No roads | Not run | |
| 8 | 200,000 places | Not run | |
| 9 | A long chain | Not run |