CONN-P1

The junction's group

Practice 1 of 4Connectivity10 tests

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

  1. Hint 1Nudge
  2. Hint 2Approach Open hint 1 first
  3. Hint 3Pseudocode Open hint 2 first
  4. Worked solutionlast resort Opens after all 3 hints
Python waits for a wider screensolution.py

Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.

10 tests, not run yet
Test results
#TestResultReads · time
1The exampleNot run
2Nobody comes backNot run
3The last groupNot run
4Loops and repeated streetsNot run
5One junctionNot run
6Sorted answerNot run
7A ring of 100,000Not run
8A long one-way chainNot run
9100,000 random streetsNot run
1020,000 small groupsNot run