All Paths from Source Lead to Destination

How it works

We need to verify two conditions: every path from the source eventually reaches the destination, and there are no cycles that would create infinite paths. A DFS with cycle detection handles both.

We use a three-color marking scheme. Nodes start unvisited (white). When we begin processing a node, we mark it gray. When all its descendants have been fully explored, we mark it black. If we ever encounter a gray node during traversal, we've found a back edge, meaning there's a cycle.

A leaf node (no outgoing edges) must be the destination. If we find any leaf that isn't the destination, or any cycle, we return false.

Steps

1. Build an adjacency list from the edges.
2. Initialize a states array where each node starts as unvisited (null or 0).
3. Run DFS from the source node:
   • If the node is already gray, we found a cycle; return false.
   • If the node is already black, it's safe; return true.
   • If the node has no outgoing edges (leaf), check if it equals the destination.
   • Mark the node gray and recursively visit all neighbors.
   • If any neighbor returns false, return false.
   • Mark the node black and return true.
4. Return the result of dfs(source).

Complexity

• Time complexity:

  • Typically for an entire DFS over an input graph, it takes O(V + E) where V represents the number of vertices in the graph and likewise, E represents the number of edges in the graph. In the worst case E can be O(V^2) in case each vertex is connected to every other vertex in the graph. However even in the worst case, we will end up discovering a cycle very early on and prune the recursion tree. If we were to traverse the entire graph, then the complexity would be O(V^2) as the O(E) part would dominate. However, due to pruning and backtracking in case of cycle detection, we end up with an overall time complexity of O(V).

• Space complexity: O(V + E)

  • Where O(E) is occupied by the adjacency list and O(V) is occupied by the recursion stack and the color states.

Where V represents the number of vertices in the graph and E represents the number of edges in the graph.

Things to watch for

Using Simple Visited Set Instead of Three-Color Marking

A basic visited set cannot distinguish between nodes currently being processed (in the current DFS path) and nodes fully processed. This fails to detect cycles properly, as revisiting a completed node is valid but revisiting a node in the current path indicates a cycle.

Not Checking That Leaf Nodes Equal Destination

A leaf node (no outgoing edges) represents the end of a path. If any leaf is not the destination, the answer is false. Forgetting this check allows paths that end at wrong nodes to be accepted.

Treating Destination with Outgoing Edges as Valid

The destination must be a true endpoint with no outgoing edges. If the destination has outgoing edges, paths can continue beyond it, violating the requirement that all paths terminate at the destination.

Not Handling Disconnected Nodes or Unreachable Destination

If the source cannot reach the destination at all, or if some paths lead to dead ends that are not the destination, the answer should be false. Failing to explore all paths from source misses these cases.

from typing import List

class Solution:
    
    # We don't use the state WHITE as such anywhere. Instead, the "null" value in the states array below is a substitute for WHITE.
    GRAY = 1
    BLACK = 2

    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        graph = self.buildDigraph(n, edges)
        return self.leadsToDest(graph, source, destination, [None] * n)
        
    def leadsToDest(self, graph, node, dest, states):
        
        # If the state is GRAY, this is a backward edge and hence, it creates a Loop.
        if states[node] != None:
            return states[node] == Solution.BLACK
        
        # If this is a leaf node, it should be equal to the destination.
        if len(graph[node]) == 0:
            return node == dest
        
        # Now, we are processing this node. So we mark it as GRAY.
        states[node] = Solution.GRAY
        
        for next_node in graph[node]:
            
            # If we get a `false` from any recursive call on the neighbors, we short circuit and return from there.
            if not self.leadsToDest(graph, next_node, dest, states):
                return False
        
        # Recursive processing done for the node. We mark it BLACK.
        states[node] = Solution.BLACK
        return True
        
    def buildDigraph(self, n, edges):
        graph = [[] for _ in range(n)]
        
        for edge in edges:
            graph[edge[0]].append(edge[1])
            
        return graph

class Solution {
public:
    static const int GRAY = 1;
    static const int BLACK = 2;
    
    bool leadsToDestination(int n, vector<vector<int>>& edges, int source, int destination) {
        vector<vector<int>> graph = buildDigraph(n, edges);
        vector<int> states(n, 0);
        return leadsToDest(graph, source, destination, states);
    }
    
private:
    bool leadsToDest(vector<vector<int>>& graph, int node, int dest, vector<int>& states) {
        if (states[node] != 0) {
            return states[node] == BLACK;
        }
        if (graph[node].size() == 0) {
            return node == dest;
        }
        states[node] = GRAY;
        for (int next_node : graph[node]) {
            if (!leadsToDest(graph, next_node, dest, states)) {
                return false;
            }
        }
        states[node] = BLACK;
        return true;
    }
    
    vector<vector<int>> buildDigraph(int n, vector<vector<int>>& edges) {
        vector<vector<int>> graph(n);
        for (auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
        }
        return graph;
    }
};