The problem
A town has n junctions joined by one-way streets. A street (u, v) lets you drive from u to v, but not back. Return the strongly connected group of junction s: every junction v such that you can drive from s to v and also from v back to s, perhaps along many streets. List them in increasing order. Junction s is always in its own group.
streets = [(0, 1), (1, 4), (4, 0), (5, 4), (5, 6),
(1, 2), (2, 3), (3, 7), (7, 6), (6, 2)]
group_of(8, streets, 0) # [0, 1, 4]
group_of(8, streets, 5) # [5]
group_of(8, streets, 6) # [2, 3, 6, 7]
This is the town of lesson 1’s figure, with A to H as 0 to 7. A street may lead from a junction to itself, and the same street may be listed twice.
Limits
- Up to 100,000 junctions and 200,000 streets.
- A search may go 100,000 streets deep, so recursion is too deep. The big tests have 3 seconds each.
Builds on CONN-1 Strongly connected components.
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 | Nobody comes back | Not run | |
| 3 | The last group | Not run | |
| 4 | Loops and repeated streets | Not run | |
| 5 | One junction | Not run | |
| 6 | Sorted answer | Not run | |
| 7 | A ring of 100,000 | Not run | |
| 8 | A long one-way chain | Not run | |
| 9 | 100,000 random streets | Not run | |
| 10 | 20,000 small groups | Not run |