Flight Routes Check
A country has n cities, numbered 1 to n, and m one-way flights. A flight [a, b] takes you from city a to city b, and it does not take you back. A route is any sequence of flights, one after another.
Decide whether every city can reach every other city by some route. If it can, return ["YES"]. If it cannot, return ["NO", a, b], where a and b are two cities and no route leads from a to b. If several such pairs exist, any one of them is accepted.
Worked Examples
n = 3, flights = [[1,2],[2,3],[3,1]]["YES"]n = 4, flights = [[1,2],[2,3],[3,1],[1,4],[3,4]]["NO", 4, 3]⚖️Formal Constraints & Bounds
1 <= n <= 1051 <= m <= 2 * 105(the number of flights)1 <= a, b <= n
Core Insight
One depth-first search finds every group in which the cities reach each other. A city whose low equals its own disc is the first city of a group, and popping group_stack down to it collects the group. One group means every city reaches every other city. With more groups, the first group completed has no flight out, so it cannot reach any other group.
Real-World Scenario & Production Applications
Checking that a one-way network is connected in both directions: a set of one-way streets where every junction must be reachable from every other junction, or a set of services that must all be able to call each other through a chain of calls.
Step-by-Step Execution Trace Table
Step-by-Step Tarjan's Algorithm (n = 4, flights = [[1,2],[2,3],[3,1],[1,4],[3,4]])
- Step 1 (Start at 1):
disc[1] = low[1] = 1,group_stack = [1]. - Step 2 (Down to 2, then 3):
disc[2] = low[2] = 2anddisc[3] = low[3] = 3, sogroup_stack = [1, 2, 3]. - Step 3 (A Flight Back to a Waiting City): city 3 has a flight to city 1, and city 1 is on
group_stack, solow[3] = min(3, disc[1]) = 1. - Step 4 (Down to 4): city 3 also has a flight to city 4, which is new:
disc[4] = low[4] = 4andgroup_stack = [1, 2, 3, 4]. - Step 5 (City 4 Finishes): city 4 has no flight out and
low[4] == disc[4], sogroup_stackis popped down to city 4. Group 0 is {4}, andgroup_stack = [1, 2, 3]. - Step 6 (Cities 3 and 2 Finish):
low[3] = 1is notdisc[3] = 3, so city 3 stays on the stack and handslow = 1to city 2. City 2 is also not a root, and it handslow = 1to city 1. - Step 7 (City 1 Sees City 4): city 4 was reached, but it is no longer on
group_stack, soon_stack[4]is False anddisc[4]is not used. City 1 finishes withlow[1] == disc[1] == 1, so the stack is popped down to city 1. Group 1 is {3, 2, 1}. - Step 8 (Answer):
comp_id = 2, so the answer is NO. The first group completed is city 4, and no flight leaves it, sosink = 4andother = 3. Return["NO", 4, 3]✅.
n = 3, flights = [[1,2],[2,3],[3,1]]Expected:["YES"]| 1 | adj = the flights that leave each city |
| 2 | disc, low, on_stack, group_stack = the search state |
| 3 | for start in 1..n: |
| 4 | if start is not reached yet: search from start |
| 5 | a new city gets the next disc and waits on group_stack |
| 6 | a reached city that still waits lowers low[city] to its disc |
| 7 | a finished city hands its low to its parent |
| 8 | if low[city] == disc[city]: pop group_stack down to city as one group |
| 9 | return YES for one group, else NO with a city of the first group and a city outside it |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Tarjan's algorithm finds every strongly connected group of a directed graph with one depth-first search. A group is a set of cities where each city can reach every other city of the set. In Flight Routes Check, one group that holds all the cities means that every city can reach every other city.
The search gives each city a number disc when it first reaches the city, and it puts the city on a stack called group_stack. A city on this stack is waiting: it has been reached, but its group is not complete. For each city, low is the smallest disc of a waiting city that the city's subtree can reach. When a city has tried all of its flights and low[city] == disc[city], nothing below it can climb above it. That city is the first city of a group, and the search pops group_stack down to it to collect the group.
🏨 The Analogy: A Waiting Room With Numbered Tickets
Each city takes a ticket number when the search first arrives, and it sits in a waiting room. A flight from the current city to a city that still sits in the room means that the current city can fly back to an older ticket, so its group cannot leave yet. A flight to a city that already left the room leads to a group that is complete, and it is ignored. When the current city's own ticket is the smallest number it can reach, no city behind it in the room can reach an older ticket. That city and every city that arrived after it and still waits leave the room together as one group.
🔑 The Key Idea in the Code
Two lines decide the result. The line if on_stack[nxt]: lets a reached city lower low[city] only while that city still waits, because a city in a complete group cannot lead back. The line if low[city] == disc[city]: marks the first city of a group, and the loop that pops group_stack until it reaches city collects the whole group.
Kosaraju's algorithm gets the same groups with two passes and a reversed copy of the graph. Tarjan's algorithm needs one pass over the original graph, and it keeps the extra arrays low and on_stack instead.
Using
disc[nxt]for every reached city (the trap):low[city] = min(low[city], disc[nxt])must sit underif on_stack[nxt]:. A city that already leftgroup_stackis in a complete group, and using it keepscityfrom being popped.Clearing
on_stackwhen the search leaves a city: the flag stays True until the city is popped with its group. If it is cleared earlier, a later flight to a waiting city is ignored.Not handing
lowup to the parent:low[parent] = min(low[parent], low[city])comes afterpath.pop(). Without it, a flight back to an older city never reaches the cities in between.Recursive DFS at scale: with
nup to105cities, a recursive search passes Python's recursion limit on one long chain of flights. The search keeps its ownpath.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Whether every city can reach every other city" over "one-way flights": reaching each other in both directions is the definition of a strongly connected group. If the whole graph is one group, the answer is YES. If not, the answer needs a pair with no route. With up to 105 cities and 2 * 105 flights, a search from every city is too slow, so the answer has to come from one linear search.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
group_stack holds the reached cities whose group is not complete. low[city] is the smallest disc of a waiting city that city's subtree reaches. A city is the first city of its group exactly when low[city] == disc[city], and then every city above it on group_stack is in its group. The first group completed has no flight leaving it.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
Every city must reach every other city, so I check whether the graph is one strongly connected group. I use Tarjan's algorithm, which is one depth-first search. I number the cities in the order I reach them, that number is disc, and I keep a stack of cities whose group is not complete. For each city, low is the smallest disc of a waiting city that its subtree can reach. When a city finishes with low equal to disc, it is the first city of a group, so I pop the stack down to it. The trap is a flight to a city that already left the stack: I use a neighbour only while it is still on the stack. One group means YES. Otherwise the first group completed has no flight out, so I name a city from it and a city outside it. The search is iterative, and the time and space are both linear in cities plus flights.
Complexity & Mathematical Proof
O(V + E)
Look at the code: building adj touches each of the E flights once. The test disc[nxt] == 0 is True once per city, so each city gets one disc, one push on group_stack and one pop. Each frame of path has one iterator over its city's flights, so every flight is read once across the whole search, and each min takes constant time. The final loop over the cities is O(V). Total: O(V + E).
O(V + E)
adj holds E entries: O(E). disc, low, on_stack and comp hold V + 1 entries each: O(V). group_stack and path hold at most one entry per city: O(V). Nothing is recursive, so there is no hidden call-stack cost.
T(V, E) = (V + E) [build adj] + (V + E) [one search with pushes, pops and low updates] + V [final loop] = O(V + E)
Derivation Progression
E appends: O(V + E)
Every flight is added once to adj.
V pushes, V pops, E flight reads: O(V + E)
The disc[nxt] == 0 test lets each city enter the search once, and each city's iterator reads each flight once.
V steps: O(V)
The last loop reads comp once per city to find a city of the first group and a city outside it.
Variable Definitions
Number of cities, n
Number of flights, len(flights)
Memory Architecture & Bounds
O(1): the search uses an explicit path, no recursion
O(V + E): adj holds E entries; disc, low, on_stack, comp, group_stack and path hold O(V) each
O(1): the answer has at most three items
Boundary Best / Worst Cases
: every city and flight is handled once on every input.
.
.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Scale signal: checking every pair of cities with its own search costs about steps; Tarjan's algorithm with one search costs about .
, . One chain of flights makes the search path cities deep, far past a recursion limit, so the search keeps its own path. Unlike Kosaraju's algorithm, it needs no reversed copy of the flights, so memory stays at one edge list.
Use disc[nxt] only for a neighbour with on_stack[nxt] True, and clear on_stack only when the city is popped with its group. Group ids depend on the search order, so ids from two runs must never be compared. When flights are added or removed over time, groups can merge or split, so the simple production answer is to rerun the linear search.
Core Algorithmic State Invariants
- The Smallest Case: n = 2, flights = [[2, 1]]
City 1 has no flight out, so it finishes alone as group 0. City 2 has a flight to city 1, but city 1 already left group_stack, so on_stack[1] is False and low[2] stays 2. City 2 is a group of its own, comp_id is 2, and the answer is NO: no route leads from city 1 to city 2.
- One Cycle Is One Group
In n = 3, flights = [[1,2],[2,3],[3,1]], city 3 has a flight to city 1, and city 1 is on group_stack, so low[3] = 1. That value goes up to city 2 and then to city 1. Only city 1 finishes with low equal to disc, and it pops all three cities as group 0: comp_id is 1, so the answer is YES.
- The First Group Completed Has No Flight Out
A group is completed only when nothing below it climbs to an older waiting city, so every flight that leaves a city of the group leads to a group that is already complete. The first group has none to lead to. In Example 2, city 4 is group 0, so no route leads from city 4 to city 3.
Flight Routes Check
A country has n cities, numbered 1 to n, and m one-way flights. A flight [a, b] takes you from city a to city b, and it does not take you back. A route is any sequence of flights, one after another.
Decide whether every city can reach every other city by some route. If it can, return ["YES"]. If it cannot, return ["NO", a, b], where a and b are two cities and no route leads from a to b. If several such pairs exist, any one of them is accepted.
Worked Examples
n = 3, flights = [[1,2],[2,3],[3,1]]["YES"]n = 4, flights = [[1,2],[2,3],[3,1],[1,4],[3,4]]["NO", 4, 3]⚖️Formal Constraints & Bounds
1 <= n <= 1051 <= m <= 2 * 105(the number of flights)1 <= a, b <= n
Core Insight
One depth-first search finds every group in which the cities reach each other. A city whose low equals its own disc is the first city of a group, and popping group_stack down to it collects the group. One group means every city reaches every other city. With more groups, the first group completed has no flight out, so it cannot reach any other group.
Real-World Scenario & Production Applications
Checking that a one-way network is connected in both directions: a set of one-way streets where every junction must be reachable from every other junction, or a set of services that must all be able to call each other through a chain of calls.
Step-by-Step Execution Trace Table
Step-by-Step Tarjan's Algorithm (n = 4, flights = [[1,2],[2,3],[3,1],[1,4],[3,4]])
- Step 1 (Start at 1):
disc[1] = low[1] = 1,group_stack = [1]. - Step 2 (Down to 2, then 3):
disc[2] = low[2] = 2anddisc[3] = low[3] = 3, sogroup_stack = [1, 2, 3]. - Step 3 (A Flight Back to a Waiting City): city 3 has a flight to city 1, and city 1 is on
group_stack, solow[3] = min(3, disc[1]) = 1. - Step 4 (Down to 4): city 3 also has a flight to city 4, which is new:
disc[4] = low[4] = 4andgroup_stack = [1, 2, 3, 4]. - Step 5 (City 4 Finishes): city 4 has no flight out and
low[4] == disc[4], sogroup_stackis popped down to city 4. Group 0 is {4}, andgroup_stack = [1, 2, 3]. - Step 6 (Cities 3 and 2 Finish):
low[3] = 1is notdisc[3] = 3, so city 3 stays on the stack and handslow = 1to city 2. City 2 is also not a root, and it handslow = 1to city 1. - Step 7 (City 1 Sees City 4): city 4 was reached, but it is no longer on
group_stack, soon_stack[4]is False anddisc[4]is not used. City 1 finishes withlow[1] == disc[1] == 1, so the stack is popped down to city 1. Group 1 is {3, 2, 1}. - Step 8 (Answer):
comp_id = 2, so the answer is NO. The first group completed is city 4, and no flight leaves it, sosink = 4andother = 3. Return["NO", 4, 3]✅.
n = 3, flights = [[1,2],[2,3],[3,1]]Expected:["YES"]| 1 | adj = the flights that leave each city |
| 2 | disc, low, on_stack, group_stack = the search state |
| 3 | for start in 1..n: |
| 4 | if start is not reached yet: search from start |
| 5 | a new city gets the next disc and waits on group_stack |
| 6 | a reached city that still waits lowers low[city] to its disc |
| 7 | a finished city hands its low to its parent |
| 8 | if low[city] == disc[city]: pop group_stack down to city as one group |
| 9 | return YES for one group, else NO with a city of the first group and a city outside it |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Tarjan's algorithm finds every strongly connected group of a directed graph with one depth-first search. A group is a set of cities where each city can reach every other city of the set. In Flight Routes Check, one group that holds all the cities means that every city can reach every other city.
The search gives each city a number disc when it first reaches the city, and it puts the city on a stack called group_stack. A city on this stack is waiting: it has been reached, but its group is not complete. For each city, low is the smallest disc of a waiting city that the city's subtree can reach. When a city has tried all of its flights and low[city] == disc[city], nothing below it can climb above it. That city is the first city of a group, and the search pops group_stack down to it to collect the group.
🏨 The Analogy: A Waiting Room With Numbered Tickets
Each city takes a ticket number when the search first arrives, and it sits in a waiting room. A flight from the current city to a city that still sits in the room means that the current city can fly back to an older ticket, so its group cannot leave yet. A flight to a city that already left the room leads to a group that is complete, and it is ignored. When the current city's own ticket is the smallest number it can reach, no city behind it in the room can reach an older ticket. That city and every city that arrived after it and still waits leave the room together as one group.
🔑 The Key Idea in the Code
Two lines decide the result. The line if on_stack[nxt]: lets a reached city lower low[city] only while that city still waits, because a city in a complete group cannot lead back. The line if low[city] == disc[city]: marks the first city of a group, and the loop that pops group_stack until it reaches city collects the whole group.
Kosaraju's algorithm gets the same groups with two passes and a reversed copy of the graph. Tarjan's algorithm needs one pass over the original graph, and it keeps the extra arrays low and on_stack instead.
Using
disc[nxt]for every reached city (the trap):low[city] = min(low[city], disc[nxt])must sit underif on_stack[nxt]:. A city that already leftgroup_stackis in a complete group, and using it keepscityfrom being popped.Clearing
on_stackwhen the search leaves a city: the flag stays True until the city is popped with its group. If it is cleared earlier, a later flight to a waiting city is ignored.Not handing
lowup to the parent:low[parent] = min(low[parent], low[city])comes afterpath.pop(). Without it, a flight back to an older city never reaches the cities in between.Recursive DFS at scale: with
nup to105cities, a recursive search passes Python's recursion limit on one long chain of flights. The search keeps its ownpath.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Whether every city can reach every other city" over "one-way flights": reaching each other in both directions is the definition of a strongly connected group. If the whole graph is one group, the answer is YES. If not, the answer needs a pair with no route. With up to 105 cities and 2 * 105 flights, a search from every city is too slow, so the answer has to come from one linear search.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
group_stack holds the reached cities whose group is not complete. low[city] is the smallest disc of a waiting city that city's subtree reaches. A city is the first city of its group exactly when low[city] == disc[city], and then every city above it on group_stack is in its group. The first group completed has no flight leaving it.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
Every city must reach every other city, so I check whether the graph is one strongly connected group. I use Tarjan's algorithm, which is one depth-first search. I number the cities in the order I reach them, that number is disc, and I keep a stack of cities whose group is not complete. For each city, low is the smallest disc of a waiting city that its subtree can reach. When a city finishes with low equal to disc, it is the first city of a group, so I pop the stack down to it. The trap is a flight to a city that already left the stack: I use a neighbour only while it is still on the stack. One group means YES. Otherwise the first group completed has no flight out, so I name a city from it and a city outside it. The search is iterative, and the time and space are both linear in cities plus flights.
Complexity & Mathematical Proof
O(V + E)
Look at the code: building adj touches each of the E flights once. The test disc[nxt] == 0 is True once per city, so each city gets one disc, one push on group_stack and one pop. Each frame of path has one iterator over its city's flights, so every flight is read once across the whole search, and each min takes constant time. The final loop over the cities is O(V). Total: O(V + E).
O(V + E)
adj holds E entries: O(E). disc, low, on_stack and comp hold V + 1 entries each: O(V). group_stack and path hold at most one entry per city: O(V). Nothing is recursive, so there is no hidden call-stack cost.
T(V, E) = (V + E) [build adj] + (V + E) [one search with pushes, pops and low updates] + V [final loop] = O(V + E)
Derivation Progression
E appends: O(V + E)
Every flight is added once to adj.
V pushes, V pops, E flight reads: O(V + E)
The disc[nxt] == 0 test lets each city enter the search once, and each city's iterator reads each flight once.
V steps: O(V)
The last loop reads comp once per city to find a city of the first group and a city outside it.
Variable Definitions
Number of cities, n
Number of flights, len(flights)
Memory Architecture & Bounds
O(1): the search uses an explicit path, no recursion
O(V + E): adj holds E entries; disc, low, on_stack, comp, group_stack and path hold O(V) each
O(1): the answer has at most three items
Boundary Best / Worst Cases
: every city and flight is handled once on every input.
.
.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Scale signal: checking every pair of cities with its own search costs about steps; Tarjan's algorithm with one search costs about .
, . One chain of flights makes the search path cities deep, far past a recursion limit, so the search keeps its own path. Unlike Kosaraju's algorithm, it needs no reversed copy of the flights, so memory stays at one edge list.
Use disc[nxt] only for a neighbour with on_stack[nxt] True, and clear on_stack only when the city is popped with its group. Group ids depend on the search order, so ids from two runs must never be compared. When flights are added or removed over time, groups can merge or split, so the simple production answer is to rerun the linear search.
Core Algorithmic State Invariants
- The Smallest Case: n = 2, flights = [[2, 1]]
City 1 has no flight out, so it finishes alone as group 0. City 2 has a flight to city 1, but city 1 already left group_stack, so on_stack[1] is False and low[2] stays 2. City 2 is a group of its own, comp_id is 2, and the answer is NO: no route leads from city 1 to city 2.
- One Cycle Is One Group
In n = 3, flights = [[1,2],[2,3],[3,1]], city 3 has a flight to city 1, and city 1 is on group_stack, so low[3] = 1. That value goes up to city 2 and then to city 1. Only city 1 finishes with low equal to disc, and it pops all three cities as group 0: comp_id is 1, so the answer is YES.
- The First Group Completed Has No Flight Out
A group is completed only when nothing below it climbs to an older waiting city, so every flight that leaves a city of the group leads to a group that is already complete. The first group has none to lead to. In Example 2, city 4 is group 0, so no route leads from city 4 to city 3.