You are given an undirected graph with n nodes labeled 1 to n and an array edges, where edges[i] = [a, b] is an existing connection. The list may contain duplicate connections and self-loops.
You may add new connections between any pairs of nodes. Make the whole graph connected, with every node reachable from every other, using as few new connections as possible.
Return the minimum number of new connections required.
Examples
Example 1
Input: n = 4, edges = [[1,2],[3,4]]
Output: 1
Explanation: The graph has two connected components, {1,2} and {3,4}. One new connection between them (for example 2-3) connects everything.
Example 2
Input: n = 5, edges = []
Output: 4
Explanation: Five isolated nodes form five components; connecting k components needs k - 1 new connections.
Constraints
1≤n≤105
0≤edges.length≤2⋅105
edges[i].length=2
1≤a,b≤n
Loading editor...
Log in to run your code. Your draft is saved in this browser.Log inSign up