Min Edge Movements to Connect a Graph

Problem Overview

Moving an edge removes it from one place and adds it between two components.

Intuition

Moving an edge removes it from one place and adds it between two components. Connecting c components needs c-1 bridges. If the graph has fewer than n-1 edges altogether, you cannot build a spanning tree no matter how you rearrange, so the answer is -1. Otherwise DFS (or Union-Find) counts components and returns components - 1.

Algorithm

1If edges.length < n - 1 return -1.
2Build an undirected adjacency list from edges.
3DFS/BFS from every unvisited node; each start increments the component count.
4Return componentCount - 1.

Example Walkthrough

Input: n = 4, edges = [[0,1],[0,2],[1,2]]

1. 3 edges >= 4-1, so rearranging is possible.
2. Components: {0,1,2} and {3} -> 2 components.
3. Need 2 - 1 = 1 move to attach node 3.

Output: 1

Common Pitfalls

• Check the n-1 edge budget before counting components.
• Extra edges inside a component are the ones you "move" - you do not need to model the moves explicitly.
• Treat the graph as undirected when building adjacency.
• Isolated nodes each count as their own component.

Min Edge Movements to Connect a Graph.java

Java

// Approach: Moving an edge means removing it from one place and adding it
// elsewhere. To connect c components you need c-1 new bridges. If the graph
// already has fewer than n-1 edges total, there are not enough edges to form a
// tree even after rearranging, so return -1. Otherwise DFS/BFS count components
// and answer is components - 1.
// Time: O(n + m) Space: O(n + m)
import java.util.*;

class Solution {

    int minEdgesReq(int n, int[][] edges) {
        if (edges.length < n - 1) {
            return -1;
        }

        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] e : edges) {
            int a = e[0];
            int b = e[1];
            adj.get(a).add(b);
            adj.get(b).add(a);
        }
        boolean[] vis = new boolean[n];
        int com = 0;
        for (int i = 0; i < n; i++) {
            if (!vis[i]) {
                com++;
                dfs(adj, vis, i);
            }
        }
        return com - 1;
    }

    public void dfs(ArrayList<ArrayList<Integer>> adj, boolean[] vis, int src) {
        vis[src] = true;
        for (Integer v : adj.get(src)) {
            if (!vis[v]) {
                dfs(adj, vis, v);
            }
        }
    }
}

Was this solution helpful?