# All Paths from Source Lead to Destination  ## Intuition

• DFS from source to find all verteses could be reached from source as set 1
• Reverse the graph
• DFS from destination to see if all verteses in set 1 could be reached from destination

## Solution

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

def add_edge(self, p, q):

def reverse(self):
reverse = DiGraph(self.size)
for p in range(self.size):
for q in self.adj[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:

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

``````