NeetCode #606LC-1059MediumGraphsNC Algo100
← Back to All Problems#606 · #1059 · All Paths from Source Lead to Destination(从始点到终点的所有路径)
📌 Problem Statement & Constraints
You are given
n nodes, a list of directed edges, and source and destination. Return true if every path from source eventually reaches destination; that is, all paths from source end at destination. Constraints: 1 <= n <= 10^4, 0 <= edges.length <= 10^4.💡 Core Algorithmic Approaches
- The condition fails if either (a) some node reachable from
sourcehas no outgoing edge and is notdestination, or (b)destinationis reachable fromsourcebutsourceis not reachable fromdestination. - So: BFS/DFS from
sourceand check that every visited node either isdestinationor has an outgoing edge. - Then BFS/DFS from
destinationand check thatsourceis reachable. - Both conditions together are exactly the statement.
💻 Benchmark Python3 Implementation
class Solution:
def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
from collections import defaultdict
g = defaultdict(list)
for a, b in edges:
g[a].append(b)
state = [0] * n # 0 = unvisited, 1 = on stack, 2 = verified
def dfs(node: int) -> bool:
if state[node] == 1:
return False # cycle -> a path never ends
if state[node] == 2:
return True
if not g[node]:
return node == destination # a dead end must be the destination
state[node] = 1
for nxt in g[node]:
if not dfs(nxt):
return False
state[node] = 2
return True
return dfs(source)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(V + E): each node and edge is visited once.
💾 Space Complexity
O(V + E) for the graph and the state array.
⚠️ Interview Pitfalls & Follow-ups
- Only checking that
destinationis reachable: the condition is about all paths. - Forgetting the cycle check: a cycle reachable from
sourcemeans some path never ends. - Treating any dead end as acceptable: a dead end must be exactly the destination.
- Only exploring from
source: the DFS fromsourcedoes cover everything reachable, which is sufficient -- the "destination leads back to source" formulation is an equivalent alternative.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.