Loading problems...
TL;DR: Use Depth First Search (DFS) with three-state coloring (Unvisited, Visiting, Visited) to detect cycles and ensure all reachable paths terminate strictly at the target node.
The problem asks us to determine if, starting from a specific source node in a directed graph, every possible path we take eventually ends at the destination node. This imposes three specific conditions:
source to destination.destination.This is a classic graph reachability and validation problem, often referred to as finding "safe states" or validating strict path termination. It is a popular interview question because it tests the ability to handle cycles in directed graphs efficiently.
A naive approach would be to simulate every possible path from the source using simple recursion. For every neighbor of the current node, we recursively attempt to reach the end.
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:
false.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:
destination and has no outgoing edges (it is a valid sink).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):
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).
v has no outgoing edges: We check if v == destination. If not, the path failed.u and confirm they all lead to destination, we mark u as "Visited" (Black) and backtrack.
Let's trace the algorithm with a simple example: source = 0, destination = 2, Edges: 0->1, 1->2.
dfs(0).0 becomes Visiting (Gray).0. Neighbor is 1.dfs(1).1 becomes Visiting (Gray).1. Neighbor is 2.dfs(2).2 becomes Visiting (Gray).2 has no outgoing edges.2 == destination? Yes.2 as Verified (Black).true.2 returned true. No other neighbors.1 as Verified (Black).true.1 returned true. No other neighbors.0 as Verified (Black).true.true.The algorithm produces the correct answer based on the following invariants:
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.destination, the condition "leads to destination" is violated. This enforces that all paths terminate specifically at destination.Verified, we know all paths from it lead to destination. Re-using this result prevents redundant work without affecting correctness.cppclass 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; } };
javaimport 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; } }
pythonfrom 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)
Time Complexity:
Space Complexity:
The Graph DFS - Cycle Detection pattern is highly reusable. Understanding the 3-state coloring technique is essential for solving these related LeetCode problems:
Why did I get Time Limit Exceeded (TLE)?
Why did my solution fail on a graph with a loop?
visited sets only track if a node was ever seen, not if it is part of the current path causing a cycle.Why does source == destination return false?
source == destinationtruedestinationdestinationWhy check adj[node] is empty instead of node == destination first?
destination is enough to return true.destination. If destination has outgoing edges, the path continues.true for a path source -> destination -> bad_node.