Solution Explanation

This problem asks whether all paths from a source node eventually lead to a destination node in a directed graph. This requires checking two conditions:

1. Reachability: There must be at least one path from the source to the destination.
2. No cycles or dead ends: All paths from the source must terminate at the destination; there shouldn't be any cycles or paths that end at nodes other than the destination (nodes with no outgoing edges).

The most efficient approach is Depth-First Search (DFS) with memoization (dynamic programming) to avoid revisiting nodes and detecting cycles.

Algorithm

1. Graph Representation: The input edges is converted into an adjacency list representation of the graph. This allows efficient access to the neighbors of each node.

2. DFS with Memoization: A recursive DFS function dfs(i) is used to explore the graph starting from node i.

   • Base Cases:

     • If i is the destination, it returns true only if i has no outgoing edges (it's a terminal node).
     • If i is already visited (vis[i]) or i has no outgoing edges (g[i] is empty), it returns false (indicates a cycle or a dead end other than the destination).

   • Recursive Step:

     • Marks i as visited (vis[i] = true).
     • Recursively calls dfs(j) for each neighbor j of i.
     • If any recursive call returns false, it means a cycle or a dead end is encountered, so it returns false.
     • If all recursive calls return true, it means all paths from i eventually reach the destination, so it returns true.

3. Initialization: The vis array (or a set in Python) keeps track of visited nodes. The DFS is initiated from the source node.

Time and Space Complexity

• Time Complexity: O(V + E), where V is the number of vertices (nodes) and E is the number of edges. This is because each node and edge is visited at most once during the DFS traversal. The memoization significantly improves the performance by preventing redundant computations.

• Space Complexity: O(V) in the worst case. This is primarily due to the recursion stack during the DFS, which can grow up to the depth of the graph. The vis array (or set) also takes O(V) space. The adjacency list takes O(V + E) space, but this is considered part of the input.

Code Examples (with detailed comments)

Python:

from collections import defaultdict, deque
 
class Solution:
    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        graph = defaultdict(list) # Adjacency list to represent the graph
        for u, v in edges:
            graph[u].append(v)
 
        visited = set() # Keep track of visited nodes to detect cycles
 
        def dfs(node):
            if node in visited: # Cycle detected
                return False
            if len(graph[node]) == 0: # Reached a terminal node
                return node == destination
            
            visited.add(node) #Mark current node as visited
            for neighbor in graph[node]:
                if not dfs(neighbor): # If any path doesn't lead to the destination
                    return False
            visited.remove(node) # Backtrack: remove from visited after exploring all paths from this node.
            return True
 
        return dfs(source)

Java:

import java.util.*;
 
class Solution {
    private List<Integer>[] graph;
    private Set<Integer> visited;
 
    public boolean leadsToDestination(int n, int[][] edges, int source, int destination) {
        graph = new List[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            graph[edge[0]].add(edge[1]);
        }
        visited = new HashSet<>();
        return dfs(source, destination);
    }
 
    private boolean dfs(int node, int destination) {
        if (visited.contains(node)) {
            return false; // Cycle detected
        }
        if (graph[node].isEmpty()) {
            return node == destination; // Reached a terminal node
        }
        visited.add(node);
        for (int neighbor : graph[node]) {
            if (!dfs(neighbor, destination)) {
                return false; // If any path doesn't lead to the destination
            }
        }
        visited.remove(node); //Backtrack
        return true;
    }
}

The C++ and Go solutions would follow a very similar structure, using the same algorithmic approach and data structures. The primary differences would be in syntax and standard library usage. The core logic of DFS with memoization remains the same across all languages.