Find Active Graph Nodes and a Connectivity Plan
Amazon● MediumNEW GRADONSITE INTERVIEWProblem statement
An undirected graph has nodes 0 through n-1. First find every node reachable from start.
Return a matrix whose first row is the sorted reachable-node list. Each later row is an edge to add so the entire graph becomes connected. Use the smallest node in the start component as one endpoint and connect it to the smallest node of every other component, processing components by their smallest node. Return an empty matrix when n=0.
Function
buildConnectivityPlan(n: int, edges: int[][], start: int) → int[][]Examples
Example 1
n = 6edges = [[0,1],[1,2],[3,4]]start = 1return = [[0,1,2],[0,3],[0,5]]The active component is [0,1,2], then edges 0-3 and 0-5 connect the others.
Example 2
n = 3edges = [[0,1],[1,2]]start = 2return = [[0,1,2]]The graph is already connected, so only the active row is returned.
Example 3
n = 0edges = []start = 0return = []An empty graph has no rows.
Constraints
0 <= n <= 100000.0 <= edges.length <= 200000.- Edges have distinct valid endpoints.