Number of operations to make network connected

Given a graph with n vertices and m edges. The graph is represented by an array Edges, where Edge[i] = [a, b] indicates an edge between vertices a and b. One edge can be removed from anywhere and added between any two vertices in one operation. Find the minimum number of operations that will be required to make the graph connected. If it is not possible to make the graph connected, return -1.

1. DFS Based#

The key observation is that to connect C isolated components into one you need exactly C-1 edges, and each move reuses one edge already in the graph. So if the graph has fewer than n-1 edges overall there aren't enough edges to redistribute, and the answer is -1. Otherwise, we count connected components using DFS — each time we start a new DFS from an unvisited node we've found a new component — and the answer is simply components - 1. DFS visits each node and edge once, giving O(n + m) time with O(n) auxiliary space for the visited array and recursion stack.

class Solution{
public:

    void dfs(vector<vector<int>> &adj, vector<bool> &visited, int currNode){
        visited[currNode] = true;

        for(auto nextNode: adj[currNode]){
            if(!visited[nextNode])
                dfs(adj, visited, nextNode);
        }
    }

    int solve(int n, vector<vector<int>> &Edge){
        vector<vector<int>> adj(n);

        if(Edge.size() < n-1)
            return -1;
        for(auto edge: Edge)
        {
            int u = edge[0];
            int v = edge[1];

            adj[u].push_back(v);
            adj[v].push_back(u);
        }

        vector<bool> visited(n, false);
        int cc = 0;
        for(int i=0;i<n;i++){
            if(!visited[i]){
                cc++;
                dfs(adj, visited, i);
            }   
        }

        return cc-1;
    }
};

Time Complexity:O(n + m), where n is the number of nodes and m is the number of edges.

Space Complexity:O(n), due to the visited array and recursion stack in the worst-case.

Disjoint Set Based#

Union-Find reaches the same answer more elegantly: each node starts as its own component, and processing every edge with Unite merges two components and decrements components. After all edges are processed, components - 1 is the number of additional edges (moves) needed — no separate component-counting loop required. With path compression and union by rank, each find and Unite operation runs in amortised O(α(n)) time, making the total O(m * α(n)) — practically linear — compared to DFS's O(n + m). The trade-off is that Union-Find is slightly harder to extend to problems that need the actual path between nodes.

class UnionFind {
public:

    vector<int> parent, rank;
    int components;

    UnionFind(int n){
        parent.resize(n+1);
        rank.resize(n+1, 0);
        components=n;
        for(int i=0;i<=n;i++)
            parent[i]=i;
    }

    int find(int x)
    {
        if(x==parent[x])
            return x;
        return parent[x] = find(parent[x]);
    }

    void Unite(int x, int y){
        int xRep = find(x);
        int yRep = find(y);

        if(xRep == yRep)
            return;

        if(rank[xRep] > rank[yRep]){
            parent[yRep]= xRep;
        }else if(rank[xRep] < rank[yRep]){
            parent[xRep] = yRep;
        }else{
            parent[yRep]= xRep;
            rank[xRep]++;
        }

        components--;
    }
};

class Solution{
public:
    int solve(int n, vector<vector<int>> &Edge){
        UnionFind uf(n);

        if(Edge.size() < n-1)
            return -1;

        for(auto edge: Edge){
            int u = edge[0];
            int v = edge[1];

            uf.Unite(u,v);
        }
        return uf.components-1;
    }
};

Time Complexity:O(m * alpha(n)), where m is the number of edges and alpha(n) is the inverse Ackermann function, which grows very slowly.

Space Complexity:O(n) due to the parent and rank vectors in the UnionFind data structure.

Comparison#