Everything Reachable
An undirected graph has n nodes numbered 0 to n - 1. edges is a list of pairs [a, b], each an edge that can be walked in both directions. The same pair may appear more than once, and a may equal b (an edge from a node to itself changes nothing).
Return every node that can be reached from start by walking along zero or more edges, in increasing order. The result always contains start itself, so it is never empty.
Example 1
n 6
edges [[0,1],[1,2],[3,4]]
start 0
returns [0,1,2]
From 0 you can walk to 1 and on to 2; nodes 3, 4 and 5 are cut off.
Example 2
n 4
edges [[2,3]]
start 1
returns [1]
Node 1 has no edge at all, so only 1 itself is reachable.
Constraints
1 <= n <= 500 <= len(edges) <= 1000 <= a, b <= n - 10 <= start <= n - 1
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Graphs problems
- Farthest VillageEasy
- Fewest HopsEasy
- Follow the ArrowsEasy
- Forms a TreeEasy
- Groups After Each MergeEasy
- Largest CrowdEasy
- Loop in the WiringEasy
- Mutual FollowsEasy