All Paths From Source Lead to Destination

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

1. 1Build an adjacency list and a color array where every node starts white (unvisited).
2. 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.
3. 3If the node has no outgoing edges, return whether it equals destination, since this is where a path terminates.
4. 4Otherwise mark the node gray, recurse into every successor, and fail fast if any successor is not good.
5. 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)