#06MediumData Structures · 47% acceptance

Lab Network Reachability

GraphBFSDFS

Given a directed graph as an adjacency list and two nodes `src` and `dst`, return whether there is a path from `src` to `dst`.

Reagent dependency chains, citation graphs, pathway maps — all of these are graphs. Traversal is how you query them.

Examples

Input: graph = {0:[1,2], 1:[3], 2:[3], 3:[]}, src=0, dst=3

Output: true

Input: same graph, src=3, dst=0

Output: false

Constraints

·Nodes are labeled 0..n-1.
·The graph may contain cycles.

Hints

solution.pyPython 3

from collections import deque

def can_reach(graph, src, dst):
    seen = {src}
    q = deque([src])
    while q:
        node = q.popleft()
        if node == dst:
            return True
        for nxt in graph[node]:
            if nxt not in seen:
                seen.add(nxt)
                q.append(nxt)
    return False

Test console

// hit Run to execute the sample tests

// Interactive editor preview. Live code execution arrives with your early-access cohort.