visited = set()
def dfs(u):
if u == destination:
return True
if u in visited:
return False
visited.add(u)
for v in adj[u]:
if (dfs(v)):
return True
return False
return dfs(source)
stack = [source]
visited = set()
while stack:
u = stack.pop()
if u == destination:
return True
if u in visited:
continue
visited.add(u)
for v in adj[u]:
stack.append(v)
return False
Problems#
332. Reconstruct Itinerary#
adj = defaultdict(list)
for u, v in tickets:
adj[u].append(v)
for u, nei in adj.items():
nei.sort(reverse=True)
res = []
def dfs(u):
nonlocal res
while adj[u]:
nxt = adj[u].pop()
dfs(nxt)
res.append(u)
dfs('JFK')
return res[::-1]
1059. All Paths from Source Lead to Destination#
adj = defaultdict(list)
for u, v in edges:
adj[u].append(v)
white, gray, black = 0, 1, 2
colors = [white] * n
def dfs(u):
nonlocal white, gray, black
if colors[u] == black:
return True
if colors[u] == gray:
# loop
return False
if not adj[u]:
# leaf
return u == destination
colors[u] = gray
for v in adj[u]:
ret = dfs(v)
if not ret:
return False
colors[u] = black
return True
return dfs(source)