380. Making Wired Connections

There are n computers (0-indexed) that need to be connected into one network. Given m existing direct connections (some of which may be redundant), find the minimum number of operations needed to make every computer reachable from every other, where one operation disconnects an existing wire and reconnects it between any two computers you choose. Print -1 if it's impossible (not enough wires exist to connect everything, regardless of how they're rearranged).

Input: The first line contains n, the number of computers. The second line contains m, the number of existing connections. Each of the next m lines contains two integers, a direct connection between two computers. Output: Print a single integer - the minimum number of reconnection operations needed, or -1 if it's impossible.

1 <= n <= 10^5

The feasibility check (redundant wires >= components - 1) is really just a restatement of a basic counting fact: connecting k components into 1 always needs exactly (k-1) NEW connecting wires, and those must come from somewhere - only redundant wires are truly 'spare' and available to repurpose.

Find the minimum number of wire-moving operations to connect all computers into one network, or determine it's impossible. Brute force: Try every possible way of rewiring connections directly and check feasibility - this is combinatorially expensive, when counting components and redundant wires directly gives the answer through simple arithmetic. Optimised: The number of operations needed to merge k separate components into one is ALWAYS exactly (k-1), regardless of which specific wires get moved - and since a REDUNDANT wire (one within an already-connected component) can be freely repurposed to bridge two SEPARATE components, simply counting redundant wires and comparing to (k-1) directly determines both feasibility and the exact answer.

Walk through all n computers once, and whenever an unvisited computer is found, run a single BFS or DFS from it to mark every computer in its group as visited, incrementing a component counter each time this happens. This finds the exact same connected groups as the brute-force approach but touches every wire and every computer only once in total instead of once per starting node. If the number of wires m is less than n-1 there are not enough wires to ever connect everyone, so print -1; otherwise the answer is (number of groups - 1), since each operation can splice one redundant wire between two different groups. Time: O(n + m) Space: O(n + m)

Initialize each computer as its own singleton set, then process every wire by union-ing the sets of its two endpoints, using union by rank and path compression so each union/find call runs in near-constant time. After processing all wires, the number of distinct remaining sets is the number of connected groups, and the answer is (groups - 1) if m is at least n-1, otherwise -1. This achieves essentially linear time with very small constants and, unlike a plain traversal, extends naturally if the problem later needs to know which specific wires are redundant. Time: O((n + m) * α(n)) Space: O(n)

For every computer, run a fresh BFS or DFS from it to discover every computer it can currently reach, and use these repeated searches to work out how the n computers split into connected groups. This is correct because reachability under the existing wires exactly defines the groups that are already fully connected, but recomputing reachability from every single node wastes enormous effort since most of that work is repeated across nodes in the same group. Time: O(n * (n + m)) Space: O(n)

1. Count the graph's CONNECTED COMPONENTS using the given wires - if there are k components, exactly (k-1) operations are needed to link them all into one, PROVIDED enough spare wire exists. 2. A 'redundant' wire is one connecting two computers ALREADY in the same component (it doesn't reduce the component count) - each redundant wire is free to be moved elsewhere. 3. If the number of redundant wires is LESS than (components - 1), there simply isn't enough wire to finish the job - print -1.

Time: O(n + m) - counting components (via BFS/DFS or union-find) and identifying redundant wires both take linear time. Space: O(n), for the visited-tracking or union-find structure.

Test when there are fewer wires than n - 1 (not enough to ever connect everything, expect -1), a graph that's already fully connected (answer 0), and n at the upper bound of 10^5.

Be ready to explain precisely why a redundant wire (connecting two already-connected computers) is 'free' to repurpose - since removing it doesn't disconnect anything, it can always be relocated to bridge a genuinely disconnected pair without any downside.