⚡Flashcard Drill➔
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

  1. The condition fails if either (a) some node reachable from source has no outgoing edge and is not destination, or (b) destination is reachable from source but source is not reachable from destination.
  2. So: BFS/DFS from source and check that every visited node either is destination or has an outgoing edge.
  3. Then BFS/DFS from destination and check that source is reachable.
  4. 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 destination is reachable: the condition is about all paths.
  • Forgetting the cycle check: a cycle reachable from source means some path never ends.
  • Treating any dead end as acceptable: a dead end must be exactly the destination.
  • Only exploring from source: the DFS from source does 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.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems