class Solution {
private:
    void dfs(int s, vector<int> adj[],vector<bool> &vis)
    {
        vis[s] = true;
        for(auto x:adj[s])
        {
            if(!vis[x])
                dfs(x,adj,vis);
        }
    }
    
    int findpar(int x, vector<int>&par)
    {
        if(par[x]==x) return x;
        
        return par[x] = findpar(par[x],par);
    }
    
    void un(int u,int v, vector<int>&par, vector<int>&rank)
    {
        u = findpar(u,par);
        v = findpar(v,par);
        if(u==v) return;
        
        if(rank[u]>rank[v])
        {
            par[v] = u;
        }
        else if(rank[u]<rank[v])
        {
            par[u] = v;
        }
        else
        {
            par[u] = v;
            rank[v]++;
        }
    }
    
public:
    int makeConnected(int n, vector<vector<int>>& connections) {
        // Using DFS to count components 
        if(connections.size()<n-1) return -1;
//         int ans = 0;
//         vector<bool> vis(n,false);
//         vector<int> adj[n];
//         for(auto x:connections)
//         {
//             adj[x[0]].push_back(x[1]);
//             adj[x[1]].push_back(x[0]);
//         }
        
//         for(int i = 0;i<n;i++)
//         {
//             if(!vis[i]) {dfs(i,adj,vis);++ans;}
//         }
//         return ans-1;
        
        
        // Using Disjoint Set union ->
        vector<int> par(n,0);
        vector<int> rank(n,0);
        
        // you can assume initially there are n components, hence reduce components one by one, till you do union only if parent mismatches while doing union
        
        
        for(int i = 0;i<n;i++)
        {
            par[i] = i;
        }
        
        for(auto x:connections)
        {
            un(x[0],x[1],par,rank);
        }
        unordered_set<int> s;
        
        // either you can use set to find number of parents, i.e. no of components
        for(int i = 0;i<n;i++)
        {
            s.insert(findpar(i,par));
        }
        
        return s.size()-1;
    }
};