All Paths from Source Lead to Destination

Problem Id: 1059 Difficulty: Medium


Intuition

Solution


class DiGraph:
    def __init__(self, size):
        self.size = size
        self.adj = [[] for _ in range(size)]

    def add_edge(self, p, q):
        self.adj[p].append(q)

    def reverse(self):
        reverse = DiGraph(self.size)
        for p in range(self.size):
            for q in self.adj[p]:
                reverse.add_edge(q, p)
        return reverse


class DFSReachable:
    def __init__(self, digraph, source):
        self.visited = [False] * digraph.size
        self.dfs(digraph, source)

    def dfs(self, digraph, vertex):
        self.visited[vertex] = True
        for child in digraph.adj[vertex]:
            if not self.visited[child]:
                self.dfs(digraph, child)


class CycleDetect:
    def __init__(self, digraph, source):
        self.visited = [False] * digraph.size
        self.on_stack = [False] * digraph.size
        self.cycle = False
        self.dfs(digraph, source)

    def dfs(self, digraph, vertex):
        self.visited[vertex] = True
        self.on_stack[vertex] = True
        for child in digraph.adj[vertex]:
            if not self.visited[child]:
                self.dfs(digraph, child)
            elif self.on_stack[child]:
                self.cycle = True
        self.on_stack[vertex] = False


class Solution:
    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        digraph = DiGraph(n)
        for p, q in edges:
            digraph.add_edge(p, q)

        if CycleDetect(digraph, source).cycle:
            return False

        from_source = DFSReachable(digraph, source)

        reverse = digraph.reverse()
        from_destination = DFSReachable(reverse, destination)

        for i in range(n):
            if from_source.visited[i]:
                if not from_destination.visited[i]:
                    return False
        return True