Planets and Kingdoms
A game world has n planets and m one-way teleporters. Planets a and b belong to the same kingdom exactly when there is a route from a to b and a route back from b to a, each route following any number of teleporters in the direction they point.
The planets are numbered 1 to n. Each teleporter is a pair [a, b]: it lets you travel from planet a to planet b, never the other way, unless a separate teleporter says so. Work out which kingdom every planet belongs to: return a list whose i-th value is the kingdom label of planet i + 1. Labels run from 1 to the number of kingdoms k, so k is the largest label. Kingdoms may be labeled any way you like, as long as two planets share a label exactly when they share a kingdom.
Worked Examples
n = 5, teleporters = [[1,2],[2,3],[3,1],[3,4],[4,5],[5,4]][1, 1, 1, 2, 2]n = 3, teleporters = [[1,2],[2,3]][1, 2, 3]⚖️Formal Constraints & Bounds
1 <= n <= 1051 <= m <= 2 * 105(the number of teleporters)1 <= a, b <= n
Core Insight
If any teleporter leads from one kingdom to another, some planet of the first kingdom finishes the first pass after every planet of the second. So the unlabeled planet that finished last lies in a kingdom that no unfound kingdom leads into, and walking the transpose from it reaches exactly the planets that can reach it back: its own kingdom.
Real-World Scenario & Production Applications
Finding mutually-dependent clusters in any directed relationship: modules whose imports form cycles in a build graph, accounts that can all wire funds to each other in a payments graph, or web pages that can each be reached from every other by following links.
Step-by-Step Execution Trace Table
Step-by-Step Kosaraju's Algorithm (n = 5, teleporters = [[1,2],[2,3],[3,1],[3,4],[4,5],[5,4]])
- Step 1 (First Pass, on
adj): DFS from planet 1: 1 -> 2 -> 3 -> 1 (already visited, skip) -> 4 -> 5 -> 4 (already visited): planet 5 has no unvisited neighbor left, so it finishes first,order = [5]; then 4 finishes:order = [5, 4]; then 3:order = [5, 4, 3]; then 2:order = [5, 4, 3, 2]; then 1:order = [5, 4, 3, 2, 1]. - Step 2 (Second Pass Starts at the Last Finisher):
reversed(order) = [1, 2, 3, 4, 5]. Start at planet 1, walkradj:radj[1] = [3](from teleporter 3 -> 1),radj[3] = [2],radj[2] = [1](already labeled). Kingdom 1 = {1, 2, 3}. - Step 3 (Next Unlabeled Finisher): 2 and 3 are already labeled; 4 is not. Start at planet 4, walk
radj:radj[4] = [3, 5](3 already labeled, 5 not), so kingdom grows to include 5;radj[5] = [4](already labeled). Kingdom 2 = {4, 5}. - Step 4 (Done): Every planet has a kingdom: 1, 2, 3 -> kingdom 1; 4, 5 -> kingdom 2 ✅.
n = 5, teleporters = [[1,2],[2,3],[3,1],[3,4],[4,5],[5,4]]Expected:[1, 1, 1, 2, 2]| 1 | adj, radj = build the graph and its transpose |
| 2 | for start in 1..n: |
| 3 | if start is not visited: |
| 4 | run an iterative DFS on adj from start |
| 5 | append each node to order when it has no unvisited neighbor left |
| 6 | for node in reversed(order): # decreasing finish time |
| 7 | if node already has a label: |
| 8 | continue |
| 9 | give node a new label |
| 10 | run a DFS from node on radj and give everything it reaches the same label |
| 11 | return the labels |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Kosaraju's algorithm finds every strongly connected component of a directed graph with two depth-first passes. The first pass walks the graph as given and records each node's finish order: the order in which a DFS runs out of unvisited neighbors to descend into. The second pass walks the transpose graph -- every edge reversed -- starting from unvisited nodes in decreasing finish order. Each tree the second pass grows is exactly one strongly connected component, because of one fact about finish times: if any edge leads from group A to a different group B, some node of A finishes after every node of B. So the unlabeled node that finished last lies in a group that no other unlabeled group leads into, and walking the transpose from it reaches exactly the nodes that can reach it back in the original graph: its own group, nothing more.
🌌 The Analogy: Draining a Reservoir System From the Lowest Outlet
Picture a network of reservoirs connected by one-way spillways. The first pass is a survey: starting anywhere, follow spillways downstream and note, for each reservoir, the moment you have nothing left downstream of it to explore -- reservoirs that are true dead ends (or whose whole downstream network is already surveyed) get noted first. The second pass works backward: starting from the LAST reservoir noted that is still unassigned (no other unassigned group spills into its group), follow the spillways upstream instead. Every reservoir reached this way can flow downstream to the start (that is how you reached it walking upstream), and none of them can sit in another unassigned group, because no such group spills into the start's group -- so they are exactly one kingdom, drained together. Moving to the next unassigned reservoir (again picking the latest-noted one) always starts a fresh kingdom, because every reservoir it could drain into upstream is already claimed.
🔑 The Key Idea in the Code
Two things have to both be true for this to work. First, reversed(order) -- processing late finishers first -- guarantees that no teleporter from a kingdom not yet found leads into the starting planet's kingdom; if a lower-finishing planet were picked instead, an unfound kingdom could still lead into its kingdom, and the walk would wrongly reach across that boundary. Second, radj: walking the transpose from that starting planet reaches every planet that can reach IT in the original graph. Because of the first point, every planet this walk reaches belongs to the start's own kingdom, and every planet of that kingdom can reach the start, so the set found is exactly the group that can reach each other both ways -- a kingdom.
Walking
adjagain in the second pass (the trap): the second pass must walkradj, the transpose graph. Reusingadjretraces outward reachability and merges one-way-reachable planets into the wrong kingdom.Processing finish order forward, not reversed (the other trap):
for planet in reversed(order). Forward order can start a component at a node whose true component hasn't been found yet, and the transpose walk then crosses a boundary it shouldn't.Recording finish order on arrival instead of on exhaustion:
order.append(planet)must happen only once a planet has no unvisited neighbor left (if not advanced), never the moment it is first visited — the ordering argument only holds for true finish order.Recursive DFS at scale: with
nup to105planets, a recursive walk can overflow Python's default recursion limit on one long teleporter chain; both passes use an explicit stack.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Two planets share a kingdom exactly when "there is a route from a to b and a route back from b to a", over "one-way teleporters": mutual reachability on a directed graph is a strongly connected component question, not a plain reachability or shortest-path one. "Which kingdom every planet belongs to" asks for every group at once, with up to 105 planets and 2 * 105 teleporters, so the answer has to come from linear passes, not a search per pair.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
comp[u] == comp[v] should hold exactly when u and v can reach each other. Kosaraju's argument is on finish times: if any edge leads from group A to a different group B, some node of A finishes after every node of B. So the unlabeled node that finishes last, the next start in reversed(order), lies in a group that no unlabeled group leads into, and walking the transpose radj from it reaches exactly the nodes that can reach it back.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
The second pass walks
radj, the transpose, notadjagain:for v in radj[u]. Reusingadjfolds every node merely reachable FROM a component into it, even when the trip back doesn't exist.The second pass must start from unvisited nodes in
reversed(order)-- decreasing finish time. Starting from the front oforder(increasing finish time, or no particular order) can start the second DFS in a group that other unfound groups lead into, and the transpose walk then pulls those groups in.A node is appended to
orderonly once it has no unvisited neighbor left, not the moment it is first visited: that is finish order, and the whole argument for why the second pass can't cross an unfound boundary depends on it being finish order specifically.
The 60-Second Interview Pitch
Say this out loud before you type a single line
This is a mutual-reachability grouping question on a directed graph, so I'd find its Strongly Connected Components with Kosaraju's algorithm: two depth-first passes. The first pass walks the graph as given and records each node's finish order -- the order in which its DFS runs out of unvisited neighbors below it. The second pass walks the transpose graph, every edge reversed, starting new trees at unvisited nodes taken in decreasing finish order. Each tree the second pass grows is exactly one kingdom. The trap is picking the wrong graph or the wrong order for the second pass: it has to be the transpose, and it has to start from the latest unfinished node, or the walk can cross into a kingdom that hasn't been found yet. Both passes are iterative DFS, since a recursive one can overflow the call stack on a long chain of planets. It's
O(V + E)time andO(V + E)space.
Complexity & Mathematical Proof
O(V + E)
Look at the code: building adj and radj touches each of the E teleporters twice, O(V + E). The first pass's for start loop runs V times, but the inner while stack work, across the whole pass, visits each node once (visited guards re-entry) and scans each node's out-edges once total across all its stack frames, so the whole pass is O(V + E). The second pass is the same shape on radj: O(V + E). Building comp and slicing it is O(V). Total: O(V + E).
O(V + E)
adj and radj together hold 2E entries: O(E). visited, order, comp are each O(V). The explicit stack in either pass holds at most one frame per node on the current DFS path, O(V). Nothing is recursive, so there is no hidden call-stack cost beyond that.
T(V, E) = (V + E) [build adj, radj] + (V + E) [first pass] + (V + E) [second pass] = O(V + E)
Derivation Progression
2E appends: O(V + E)
Every teleporter is added once to adj and once to radj.
V starts, each node visited once, each out-edge scanned once: O(V + E)
The visited guard means every node's stack frame is pushed exactly once, and every edge is looked at exactly once across the whole pass.
V starts (in reversed(order)), each node visited once, each transpose edge scanned once: O(V + E)
Same shape as the first pass, run on radj instead of adj.
Variable Definitions
Number of planets, n
Number of teleporters, len(teleporters)
Memory Architecture & Bounds
O(1): both passes use an explicit stack, no recursion
O(V + E): adj and radj hold 2E entries; visited, order and comp hold O(V) each
O(V): the V kingdom labels of comp[1:]
Boundary Best / Worst Cases
: every planet and teleporter is touched once regardless of the graph's shape.
.
.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Scale signal: planets and teleporters rule out a reachability search per planet, about steps; Strongly Connected Components with two linear passes costs about .
, : adj and radj together hold entries, twice the input, and one teleporter chain can make a DFS path planets deep, far past a recursion limit, so both passes need an explicit stack.
Memory, not time, is the limit at scale: the transpose doubles the edge lists, and every explicit-stack frame holds an iterator. Component ids depend on the DFS order, so ids from two different runs (say, before and after the graph changes) must never be compared.
Core Algorithmic State Invariants
- The Smallest Case: n = 2, teleporters = [[1, 2]]
The first pass reaches 2 from 1, so 2 finishes first: order = [2, 1]. The second pass starts at 1 and radj[1] is empty, so planet 1 is a kingdom alone; then planet 2 starts its own. Two kingdoms, as there is no way back from 2 to 1.
- Planets on No Cycle
A planet with no teleporter out, or only a teleporter to itself, finishes as soon as it is reached, and the second pass from it finds no unlabeled planet that leads back: it is a kingdom of one, like every planet in Example 2.
Planets and Kingdoms
A game world has n planets and m one-way teleporters. Planets a and b belong to the same kingdom exactly when there is a route from a to b and a route back from b to a, each route following any number of teleporters in the direction they point.
The planets are numbered 1 to n. Each teleporter is a pair [a, b]: it lets you travel from planet a to planet b, never the other way, unless a separate teleporter says so. Work out which kingdom every planet belongs to: return a list whose i-th value is the kingdom label of planet i + 1. Labels run from 1 to the number of kingdoms k, so k is the largest label. Kingdoms may be labeled any way you like, as long as two planets share a label exactly when they share a kingdom.
Worked Examples
n = 5, teleporters = [[1,2],[2,3],[3,1],[3,4],[4,5],[5,4]][1, 1, 1, 2, 2]n = 3, teleporters = [[1,2],[2,3]][1, 2, 3]⚖️Formal Constraints & Bounds
1 <= n <= 1051 <= m <= 2 * 105(the number of teleporters)1 <= a, b <= n
Core Insight
If any teleporter leads from one kingdom to another, some planet of the first kingdom finishes the first pass after every planet of the second. So the unlabeled planet that finished last lies in a kingdom that no unfound kingdom leads into, and walking the transpose from it reaches exactly the planets that can reach it back: its own kingdom.
Real-World Scenario & Production Applications
Finding mutually-dependent clusters in any directed relationship: modules whose imports form cycles in a build graph, accounts that can all wire funds to each other in a payments graph, or web pages that can each be reached from every other by following links.
Step-by-Step Execution Trace Table
Step-by-Step Kosaraju's Algorithm (n = 5, teleporters = [[1,2],[2,3],[3,1],[3,4],[4,5],[5,4]])
- Step 1 (First Pass, on
adj): DFS from planet 1: 1 -> 2 -> 3 -> 1 (already visited, skip) -> 4 -> 5 -> 4 (already visited): planet 5 has no unvisited neighbor left, so it finishes first,order = [5]; then 4 finishes:order = [5, 4]; then 3:order = [5, 4, 3]; then 2:order = [5, 4, 3, 2]; then 1:order = [5, 4, 3, 2, 1]. - Step 2 (Second Pass Starts at the Last Finisher):
reversed(order) = [1, 2, 3, 4, 5]. Start at planet 1, walkradj:radj[1] = [3](from teleporter 3 -> 1),radj[3] = [2],radj[2] = [1](already labeled). Kingdom 1 = {1, 2, 3}. - Step 3 (Next Unlabeled Finisher): 2 and 3 are already labeled; 4 is not. Start at planet 4, walk
radj:radj[4] = [3, 5](3 already labeled, 5 not), so kingdom grows to include 5;radj[5] = [4](already labeled). Kingdom 2 = {4, 5}. - Step 4 (Done): Every planet has a kingdom: 1, 2, 3 -> kingdom 1; 4, 5 -> kingdom 2 ✅.
n = 5, teleporters = [[1,2],[2,3],[3,1],[3,4],[4,5],[5,4]]Expected:[1, 1, 1, 2, 2]| 1 | adj, radj = build the graph and its transpose |
| 2 | for start in 1..n: |
| 3 | if start is not visited: |
| 4 | run an iterative DFS on adj from start |
| 5 | append each node to order when it has no unvisited neighbor left |
| 6 | for node in reversed(order): # decreasing finish time |
| 7 | if node already has a label: |
| 8 | continue |
| 9 | give node a new label |
| 10 | run a DFS from node on radj and give everything it reaches the same label |
| 11 | return the labels |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Kosaraju's algorithm finds every strongly connected component of a directed graph with two depth-first passes. The first pass walks the graph as given and records each node's finish order: the order in which a DFS runs out of unvisited neighbors to descend into. The second pass walks the transpose graph -- every edge reversed -- starting from unvisited nodes in decreasing finish order. Each tree the second pass grows is exactly one strongly connected component, because of one fact about finish times: if any edge leads from group A to a different group B, some node of A finishes after every node of B. So the unlabeled node that finished last lies in a group that no other unlabeled group leads into, and walking the transpose from it reaches exactly the nodes that can reach it back in the original graph: its own group, nothing more.
🌌 The Analogy: Draining a Reservoir System From the Lowest Outlet
Picture a network of reservoirs connected by one-way spillways. The first pass is a survey: starting anywhere, follow spillways downstream and note, for each reservoir, the moment you have nothing left downstream of it to explore -- reservoirs that are true dead ends (or whose whole downstream network is already surveyed) get noted first. The second pass works backward: starting from the LAST reservoir noted that is still unassigned (no other unassigned group spills into its group), follow the spillways upstream instead. Every reservoir reached this way can flow downstream to the start (that is how you reached it walking upstream), and none of them can sit in another unassigned group, because no such group spills into the start's group -- so they are exactly one kingdom, drained together. Moving to the next unassigned reservoir (again picking the latest-noted one) always starts a fresh kingdom, because every reservoir it could drain into upstream is already claimed.
🔑 The Key Idea in the Code
Two things have to both be true for this to work. First, reversed(order) -- processing late finishers first -- guarantees that no teleporter from a kingdom not yet found leads into the starting planet's kingdom; if a lower-finishing planet were picked instead, an unfound kingdom could still lead into its kingdom, and the walk would wrongly reach across that boundary. Second, radj: walking the transpose from that starting planet reaches every planet that can reach IT in the original graph. Because of the first point, every planet this walk reaches belongs to the start's own kingdom, and every planet of that kingdom can reach the start, so the set found is exactly the group that can reach each other both ways -- a kingdom.
Walking
adjagain in the second pass (the trap): the second pass must walkradj, the transpose graph. Reusingadjretraces outward reachability and merges one-way-reachable planets into the wrong kingdom.Processing finish order forward, not reversed (the other trap):
for planet in reversed(order). Forward order can start a component at a node whose true component hasn't been found yet, and the transpose walk then crosses a boundary it shouldn't.Recording finish order on arrival instead of on exhaustion:
order.append(planet)must happen only once a planet has no unvisited neighbor left (if not advanced), never the moment it is first visited — the ordering argument only holds for true finish order.Recursive DFS at scale: with
nup to105planets, a recursive walk can overflow Python's default recursion limit on one long teleporter chain; both passes use an explicit stack.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Two planets share a kingdom exactly when "there is a route from a to b and a route back from b to a", over "one-way teleporters": mutual reachability on a directed graph is a strongly connected component question, not a plain reachability or shortest-path one. "Which kingdom every planet belongs to" asks for every group at once, with up to 105 planets and 2 * 105 teleporters, so the answer has to come from linear passes, not a search per pair.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
comp[u] == comp[v] should hold exactly when u and v can reach each other. Kosaraju's argument is on finish times: if any edge leads from group A to a different group B, some node of A finishes after every node of B. So the unlabeled node that finishes last, the next start in reversed(order), lies in a group that no unlabeled group leads into, and walking the transpose radj from it reaches exactly the nodes that can reach it back.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
The second pass walks
radj, the transpose, notadjagain:for v in radj[u]. Reusingadjfolds every node merely reachable FROM a component into it, even when the trip back doesn't exist.The second pass must start from unvisited nodes in
reversed(order)-- decreasing finish time. Starting from the front oforder(increasing finish time, or no particular order) can start the second DFS in a group that other unfound groups lead into, and the transpose walk then pulls those groups in.A node is appended to
orderonly once it has no unvisited neighbor left, not the moment it is first visited: that is finish order, and the whole argument for why the second pass can't cross an unfound boundary depends on it being finish order specifically.
The 60-Second Interview Pitch
Say this out loud before you type a single line
This is a mutual-reachability grouping question on a directed graph, so I'd find its Strongly Connected Components with Kosaraju's algorithm: two depth-first passes. The first pass walks the graph as given and records each node's finish order -- the order in which its DFS runs out of unvisited neighbors below it. The second pass walks the transpose graph, every edge reversed, starting new trees at unvisited nodes taken in decreasing finish order. Each tree the second pass grows is exactly one kingdom. The trap is picking the wrong graph or the wrong order for the second pass: it has to be the transpose, and it has to start from the latest unfinished node, or the walk can cross into a kingdom that hasn't been found yet. Both passes are iterative DFS, since a recursive one can overflow the call stack on a long chain of planets. It's
O(V + E)time andO(V + E)space.
Complexity & Mathematical Proof
O(V + E)
Look at the code: building adj and radj touches each of the E teleporters twice, O(V + E). The first pass's for start loop runs V times, but the inner while stack work, across the whole pass, visits each node once (visited guards re-entry) and scans each node's out-edges once total across all its stack frames, so the whole pass is O(V + E). The second pass is the same shape on radj: O(V + E). Building comp and slicing it is O(V). Total: O(V + E).
O(V + E)
adj and radj together hold 2E entries: O(E). visited, order, comp are each O(V). The explicit stack in either pass holds at most one frame per node on the current DFS path, O(V). Nothing is recursive, so there is no hidden call-stack cost beyond that.
T(V, E) = (V + E) [build adj, radj] + (V + E) [first pass] + (V + E) [second pass] = O(V + E)
Derivation Progression
2E appends: O(V + E)
Every teleporter is added once to adj and once to radj.
V starts, each node visited once, each out-edge scanned once: O(V + E)
The visited guard means every node's stack frame is pushed exactly once, and every edge is looked at exactly once across the whole pass.
V starts (in reversed(order)), each node visited once, each transpose edge scanned once: O(V + E)
Same shape as the first pass, run on radj instead of adj.
Variable Definitions
Number of planets, n
Number of teleporters, len(teleporters)
Memory Architecture & Bounds
O(1): both passes use an explicit stack, no recursion
O(V + E): adj and radj hold 2E entries; visited, order and comp hold O(V) each
O(V): the V kingdom labels of comp[1:]
Boundary Best / Worst Cases
: every planet and teleporter is touched once regardless of the graph's shape.
.
.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Scale signal: planets and teleporters rule out a reachability search per planet, about steps; Strongly Connected Components with two linear passes costs about .
, : adj and radj together hold entries, twice the input, and one teleporter chain can make a DFS path planets deep, far past a recursion limit, so both passes need an explicit stack.
Memory, not time, is the limit at scale: the transpose doubles the edge lists, and every explicit-stack frame holds an iterator. Component ids depend on the DFS order, so ids from two different runs (say, before and after the graph changes) must never be compared.
Core Algorithmic State Invariants
- The Smallest Case: n = 2, teleporters = [[1, 2]]
The first pass reaches 2 from 1, so 2 finishes first: order = [2, 1]. The second pass starts at 1 and radj[1] is empty, so planet 1 is a kingdom alone; then planet 2 starts its own. Two kingdoms, as there is no way back from 2 to 1.
- Planets on No Cycle
A planet with no teleporter out, or only a teleporter to itself, finishes as soon as it is reached, and the second pass from it finds no unlabeled planet that leads back: it is a kingdom of one, like every planet in Example 2.