Quick 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.

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.

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 graph always has exactly `len(edges)` 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`. ### Rules - A graph that is already connected needs `0` moves. In particular, a single node with no edges is connected. - Return only the number of moves as a single integer, not which edges are moved or where they go. The answer is uniquely determined by the input. - An edge may list its endpoints in either order: `[a, b]` and `[b, a]` describe the same edge. ### 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. Every input value and the result fit in a 32-bit signed integer. ### Example 1 - Input: `n = 6`, `edges = [[0, 1], [0, 2], [0, 3], [1, 2], [1, 3]]` - Output: `2` - Explanation: Nodes `4` and `5` are isolated, so there are three separate pieces. Moving `[1, 2]` to `[1, 4]` and `[1, 3]` to `[3, 5]` gives the connected edge set `[[0, 1], [0, 2], [0, 3], [1, 4], [3, 5]]`. No single move can join three pieces, so `2` is optimal. ### Example 2 - 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.

Constraints

  • 1 <= n <= 100000
  • 0 <= len(edges) <= 100000
  • edges[i] == [a, 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, no self-loops)
  • The result is -1 or an integer in [0, n - 1]; all values fit in a 32-bit signed integer

Examples

Input: (4, [[0, 1], [0, 2], [1, 2]])

Expected Output: 1

Input: (6, [[0, 1], [0, 2], [0, 3], [1, 2], [1, 3]])

Expected Output: 2

Hints

  1. Before counting moves, decide when the task is impossible no matter where the edges go: how many edges does any connected graph on n nodes need?
  2. Consider how much one move (remove one edge, add one edge) can change the number of connected pieces, which gives a lower bound on the answer.
  3. Which edges can be detached without splitting their own piece apart? Check whether there are always enough of them to reach that lower bound.

Community answers

Answer by janaki9sravya

def min_edge_moves(n: int, edges: list[list[int]]) -> int: if len(edges)<n-1: return -1 adjList={} for i in range(n): adjList[i]=[] for e in edges: adjList[e[0]].append(e[1]) adjList[e[1]].append(e[0]) visited=[0 for i in range(n)] def dfs(node): nonlocal visited if visited[node]==1: return visited[node]=1 for nextnode in adjList[node]: dfs(nextnode) return c=0 for i in range(n): if visited[i]==0: dfs(i) c+=1 return c-1 n=6 edges = [[0, 1], [0, 2], [0, 3], [1, 2], [1, 3]] result = min_edge_moves(n,edges) print(result) edges = [[0, 1], [0, 2], [0, 3], [1, 2]] result = min_edge_moves(n,edges) print(result) n=3 edges=[] result = min_edge_moves(n,edges) print(result) n=1 edges=[] result = min_edge_moves(n,edges) print(result) n=2 edges=[[1,0]] result = min_edge_moves(n,edges) print(result)

Loading coding console...

Show the approach

Approach

Let m = len(edges) and let c be the number of connected components (isolated nodes count as components).

Impossible case. A connected graph on n nodes needs at least n - 1 edges, and moves never change m. So if m < n - 1 the answer is -1.

Lower bound. Removing one edge can split a component into at most two pieces, and adding one edge can merge at most two pieces. A single move therefore lowers the component count by at most one, so at least c - 1 moves are required.

Achievability. A spanning forest of the current graph uses exactly n - c edges; every other edge (m - (n - c) of them) lies on a cycle, so detaching it leaves its component intact. When m >= n - 1, there are at least c - 1 such spare edges. Each move takes one spare edge and reattaches it between two different components (such a pair is never already joined), which merges them. After the move the spare count and the component count both drop by one, so the invariant spare >= c - 1 is preserved and c - 1 moves suffice.

The reference counts components with a union-find structure (union by size plus iterative path compression, so long chains never hit a recursion limit): start with n components and decrement whenever an edge joins two different roots. It returns -1 when m < n - 1 and components - 1 otherwise.

Time complexity:
O(n + m * alpha(n)), where m = len(edges)
Space complexity:
O(n)