Fewest Edge Relocations to Make an Undirected Graph Connected
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given an undirected graph with `n` nodes labeled `0` to `n - 1` and a list `edges`, where `edges[i] = [a, b]` means there is an edge between nodes `a` and `b`.
In one **move**, you may take any existing edge, detach it from its two endpoints, and reattach it between any two distinct nodes that are not currently joined by an edge. Moves never create or destroy edges, so the total number of edges always stays `len(edges)`.
Return the minimum number of moves needed to make the graph connected, meaning every node can reach every other node. If no sequence of moves can make the graph connected, return `-1`.
### Function Signature
```python
def min_edge_moves(n: int, edges: list[list[int]]) -> int:
```
### Rules
- A graph that is already connected needs `0` moves. In particular, a single node with no edges is connected.
- Only the number of moves is returned, not which edges are moved or where they go.
### Constraints
- `1 <= n <= 100000`
- `0 <= len(edges) <= 100000`
- Each `edges[i]` contains exactly two integers `a` and `b` with `0 <= a < n`, `0 <= b < n` and `a != b`.
- No two entries of `edges` describe the same unordered pair of nodes (no duplicate edges and no self-loops).
- The result is either `-1` or an integer from `0` to `n - 1` inclusive, and it is uniquely determined by the input.
### Examples
**Example 1**
- Input: `n = 4`, `edges = [[0, 1], [0, 2], [1, 2]]`
- Output: `1`
- Explanation: Moving the edge `[1, 2]` so that it joins nodes `1` and `3` leaves every node reachable from every other node. The graph starts disconnected, so at least one move is needed.
**Example 2**
- Input: `n = 6`, `edges = [[0, 1], [0, 2], [0, 3], [1, 2], [1, 3]]`
- Output: `2`
- Explanation: One optimal plan moves `[1, 2]` to `[1, 4]` and `[1, 3]` to `[3, 5]`, giving the connected edge set `[[0, 1], [0, 2], [0, 3], [1, 4], [3, 5]]`. No plan with a single move exists.
**Example 3**
- Input: `n = 6`, `edges = [[0, 1], [0, 2], [0, 3], [1, 2]]`
- Output: `-1`
- Explanation: Four edges cannot connect six nodes, however they are placed.
Overview: Given an undirected graph as a node count and an edge list, compute the fewest edge relocations needed to make every node reachable from every other, or report that it is impossible. It tests reasoning about connected components and redundant edges, and efficient graph processing on up to 100,000 nodes.
