Write reachable(n, edges, start) -> set[int]: the set of nodes you can reach from start in an undirected graph, including start itself. That set is start's connected component.
- Nodes are
0 .. n-1.edgesis a list of pairs(a, b), each an undirected edge. Edges may repeat, and self-loops(a, a)may appear. - Build an adjacency list first, then walk it with an explicit stack (a Python list), not recursion: one test is a path of 20,000 nodes, far past Python's recursion limit of about 1000.
reachable(6, [(0, 1), (1, 2), (3, 4)], 0) # {0, 1, 2}
reachable(6, [(0, 1), (1, 2), (3, 4)], 5) # {5} (no edges at all)
Constraints: 1 <= n <= 10**5, 0 <= start < n, up to 2 * 10**5 edges.
Show hint
mark a node as seen when you push it onto the stack, and only push neighbours you haven't seen, so each node is pushed at most once.