Connect Components with Edges | Dataford Interview Questions

A country has multiple disconnected cities; find the minimum number of edges required to connect all components.

Asked in the Round 4 DSA stage. Implement min_edges_to_connect(n, edges), where cities are numbered 0 through n - 1 and each edge is an undirected connection. Return the minimum number of new edges needed to make every city reachable from every other city. You may connect any two cities from different components.

Example: n = 5, edges = [[0, 1], [1, 2], [3, 4]] returns 1, because there are two components. If all cities are isolated, the answer is n - 1.

Constraints: 1 <= n <= 10^5; 0 <= len(edges) <= 2 * 10^5; endpoints are valid and no self-loops exist.

Constraints

1 <= n <= 10^5
0 <= len(edges) <= 2 * 10^5
Each edge has exactly two endpoints
0 <= edges[i][0], edges[i][1] < n
The graph is undirected and contains no self-loops

Function Signature

def min_edges_to_connect(n, edges):

Your question is Connect Components with Edges. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem