MediumGraphDepth-First SearchTopological Sort

All Paths From Source Lead to Destination

1 approach, code in every language

You are given a directed graph with n nodes labeled from 0 to n - 1, described by a list of directed edges. You are also given two nodes, source and destination.

Starting at source, consider every path that follows the edges of the graph. Determine whether all of these paths are finite and every one of them terminates exactly at destination.

Return true only when the following hold: at least one path leaves source, no reachable path can continue forever (there are no reachable cycles), and every path that can no longer be extended ends at destination. The graph may contain self-loops and parallel edges.

Example 1

Input: n = 3, edges = [[0,1],[0,2]], source = 0, destination = 2

Output: false

The path 0 -> 1 ends at node 1, which has no outgoing edges and is not the destination, so not every path leads to destination.

Example 2

Input: n = 4, edges = [[0,1],[0,2],[1,3],[2,3]], source = 0, destination = 3

Output: true

Both branches 0 -> 1 -> 3 and 0 -> 2 -> 3 terminate at node 3, and there are no cycles, so every path reaches destination.

Constraints

1 <= n <= 10^4
0 <= edges.length <= 10^4
edges[i].length == 2
0 <= from_i, to_i, source, destination <= n - 1
The given graph may have self-loops and parallel edges.

DFS with Three-Color Cycle Detection

Color nodes white, gray, and black to detect cycles and validate that every dead end is the destination.

Loading animation…

Intuition

A node is 'good' only when every path leaving it eventually stops at destination, so goodness propagates from successors back to their predecessors. During a depth-first search we color a node gray while it sits on the current path; encountering a gray node again means we found a cycle, so some path never ends and the answer is false. When we reach a node with no outgoing edges, that path has ended, and it is valid only if the node is the destination. Marking finished nodes black lets us reuse verified results and avoid revisiting subtrees. The whole graph passes only if the source node itself is good.

Algorithm walkthrough

1Build an adjacency list and a color array where every node starts white (unvisited).
2Run DFS from source: if the node is gray it lies on the current path and forms a cycle, so return false; if it is black it was already verified, so return true.
3If the node has no outgoing edges, return whether it equals destination, since this is where a path terminates.
4Otherwise mark the node gray, recurse into every successor, and fail fast if any successor is not good.
5Once all successors check out, mark the node black and return true; the final answer is the result computed for source.

Implementation

from collections import defaultdict
from typing import List

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)

        WHITE, GRAY, BLACK = 0, 1, 2
        color = [WHITE] * n

        def dfs(node: int) -> bool:
            if color[node] == GRAY:
                return False
            if color[node] == BLACK:
                return True
            if len(adj[node]) == 0:
                return node == destination
            color[node] = GRAY
            for nxt in adj[node]:
                if not dfs(nxt):
                    return False
            color[node] = BLACK
            return True

        return dfs(source)

Time

O(V + E)

Space

O(V + E)

Each node and edge is examined once thanks to the black-marking of finished nodes.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Graphs

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free