python
# Pseudo-code for Naive Approach
function solve(current_node):
    if current_node has no neighbors:
        return current_node == destination
    
    for neighbor in current_node.neighbors:
        if not solve(neighbor):
            return False
    return True

Why this fails:

1. Infinite Loops (Time Limit Exceeded): If the graph contains a cycle (e.g., A -> B -> A), the simple recursion above will enter an infinite loop, causing a Stack Overflow or Time Limit Exceeded error. The problem explicitly states that cycles reachable from the source make the result false.
2. Redundant Computations: In a dense graph without cycles, the number of paths can be exponential. A node might be visited millions of times through different paths, leading to unacceptable time complexity.

Core Insight for All Paths from Source Lead to Destination

The key intuition is that we need to validate the "future" of every node reachable from source. A node is considered "valid" if and only if:

1. It is the destination and has no outgoing edges (it is a valid sink).
2. OR, all its children are "valid" nodes, and it is not part of a cycle.

To handle cycle detection efficiently in a directed graph, we cannot rely on a simple boolean visited set. Instead, we use Three-Color DFS (or three-state tracking):

1. White (Unvisited): The node has not been processed yet.
2. Gray (Visiting): The node is currently in the recursion stack (we are currently exploring its descendants). If we encounter a Gray node during DFS, we have found a back-edge, which implies a cycle.
3. Black (Visited/Safe): The node and all its descendants have been fully explored and verified as valid. If we encounter a Black node, we can immediately return true without re-processing (memoization).

Visual Description: Imagine the recursion tree expanding from the source. As we move from node u to v, we mark u as "Visiting" (Gray).

• If v has no outgoing edges: We check if v == destination. If not, the path failed.
• If we see a neighbor that is already "Visiting" (Gray): We found a loop. The path failed.
• Once we successfully explore all neighbors of u and confirm they all lead to destination, we mark u as "Visited" (Black) and backtrack.

Execution Flow

Let's trace the algorithm with a simple example: source = 0, destination = 2, Edges: 0->1, 1->2.

1. Start: Call dfs(0).
2. Process 0:
   • State of 0 becomes Visiting (Gray).
   • Check neighbors of 0. Neighbor is 1.
   • Recurse: Call dfs(1).
3. Process 1:
   • State of 1 becomes Visiting (Gray).
   • Check neighbors of 1. Neighbor is 2.
   • Recurse: Call dfs(2).
4. Process 2:
   • State of 2 becomes Visiting (Gray).
   • 2 has no outgoing edges.
   • Check: Is 2 == destination? Yes.
   • Mark 2 as Verified (Black).
   • Return true.
5. Backtrack to 1:
   • Neighbor 2 returned true. No other neighbors.
   • Mark 1 as Verified (Black).
   • Return true.
6. Backtrack to 0:
   • Neighbor 1 returned true. No other neighbors.
   • Mark 0 as Verified (Black).
   • Return true.
7. Result: The initial call returns true.

Proof of Correctness

The algorithm produces the correct answer based on the following invariants:

1. Cycle Detection: The Visiting state ensures that if we ever encounter a node that is currently in our recursion stack, a cycle exists. Since the problem states that no path from source can enter a cycle, any such detection correctly returns false.
2. Leaf Validation: The logic explicitly checks nodes with zero out-degree. If such a node is not destination, the condition "leads to destination" is violated. This enforces that all paths terminate specifically at destination.
3. Path Completeness: By iterating through all neighbors of a node, we ensure that the condition holds for every branch of the path. If even one branch fails, the parent node is marked invalid.
4. Memoization: Once a node is marked Verified, we know all paths from it lead to destination. Re-using this result prevents redundant work without affecting correctness.

Reference Implementation

C++ Solution for LeetCode 1059

cpp
class Solution {
    // States for DFS
    enum State { UNVISITED, VISITING, VISITED };

public:
    bool leadsToDestination(int n, vector<vector<int>>& edges, int source, int destination) {
        // Build Adjacency List
        vector<vector<int>> adj(n);
        for (const auto& edge : edges) {
            adj[edge[0]].push_back(edge[1]);
        }

        vector<State> states(n, UNVISITED);
        return dfs(adj, states, source, destination);
    }

private:
    bool dfs(const vector<vector<int>>& adj, vector<State>& states, int curr, int dest) {
        // Cycle detected
        if (states[curr] == VISITING) return false;
        
        // Already verified safe
        if (states[curr] == VISITED) return true;

        // Leaf node check: must be destination
        if (adj[curr].empty()) {
            return curr == dest;
        }

        // Mark as currently visiting (Gray)
        states[curr] = VISITING;

        // Verify all outgoing paths
        for (int neighbor : adj[curr]) {
            if (!dfs(adj, states, neighbor, dest)) {
                return false;
            }
        }

        // Mark as verified (Black)
        states[curr] = VISITED;
        return true;
    }
};

Java Solution for LeetCode 1059

java
import java.util.*;

class Solution {
    // 0: Unvisited, 1: Visiting, 2: Visited
    private enum State { UNVISITED, VISITING, VISITED }

    public boolean leadsToDestination(int n, int[][] edges, int source, int destination) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
        }

        State[] states = new State[n];
        Arrays.fill(states, State.UNVISITED);

        return dfs(adj, states, source, destination);
    }

    private boolean dfs(List<List<Integer>> adj, State[] states, int curr, int dest) {
        // Cycle detected
        if (states[curr] == State.VISITING) return false;
        
        // Already verified safe
        if (states[curr] == State.VISITED) return true;

        // Leaf node check
        if (adj.get(curr).isEmpty()) {
            return curr == dest;
        }

        // Mark as visiting
        states[curr] = State.VISITING;

        // Verify all neighbors
        for (int neighbor : adj.get(curr)) {
            if (!dfs(adj, states, neighbor, dest)) {
                return false;
            }
        }

        // Mark as verified
        states[curr] = State.VISITED;
        return true;
    }
}

Python Solution for LeetCode 1059

python
from collections import defaultdict

class Solution:
    def leadsToDestination(self, n: int, edges: list[list[int]], source: int, destination: int) -> bool:
        adj = defaultdict(list)
        for u, v in edges:
            adj[u].append(v)
            
        # 0: Unvisited, 1: Visiting, 2: Visited
        states = [0] * n
        
        def dfs(node):
            # Cycle detected
            if states[node] == 1:
                return False
            # Already verified
            if states[node] == 2:
                return True
            
            # Leaf node check
            if not adj[node]:
                return node == destination
            
            # Mark as visiting (Gray)
            states[node] = 1
            
            # Explore all neighbors
            for neighbor in adj[node]:
                if not dfs(neighbor):
                    return False
            
            # Mark as visited (Black)
            states[node] = 2
            return True

        return dfs(source)