All Paths from Source Lead to Destination — LeetCode 1059 Python Solution

The problem

Given the edges of a directed graph where edges[i] = [ai, bi] indicates there is an edge between nodes ai and bi, and two nodes source and destination of this graph, determine whether or not all paths starting from source eventually, end at destination, that is: At least one path exists from the source node to the destination node If a path exists from the source node to a node with no outgoing edges, then that node is equal to destination. The number of possible paths from source to destination is a finite number.

Example

Input

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

Output

false

Explanation

It is possible to reach and get stuck on both node 1 and node 2.

Python solution

class Solution:
    def leadsToDestination(
        self, n: int, edges: List[List[int]], source: int, destination: int
    ) -> bool:
        def dfs(i: int) -> bool:
            if st[i]:
                return st[i] == 2
            if not g[i]:
                return i == destination

            st[i] = 1
            for j in g[i]:
                if not dfs(j):
                    return False
            st[i] = 2
            return True

        g = [[] for _ in range(n)]
        for a, b in edges:
            g[a].append(b)
        if g[destination]:
            return False

        st = [0] * n
        return dfs(source)

Complexity

Pattern: Topological Sort

Order a set of tasks so that every dependency comes before the thing that needs it. LeetCode 1059. All Paths from Source Lead to Destination is filed here because LeetCode tags it Topological Sort, which is the vocabulary this hub collects.

The topological sort guide has the Python template for the pattern and the 32 LeetCode problems that use it.

Related problems