---
title: 1319. Number of Operations to Make Network Connected

tags: graph
description: share source code.
---

# 1319. Number of Operations to Make Network Connected

class Solution {
    
    static class UnionFind{
        int root []; 
        int rank [];
        int component;
        

        public UnionFind(int n){
            this.root = new int [n];
            this.rank = new int [n];
            this.component = n;
            
            for(int i = 0; i < n; i++){
                root [i] = i;
                rank [i] = 1;
            }

        } 

        public boolean isConnected(int u, int v){
            return find(u) == find(v);
        }

        public void merge(int u, int v){
            int pu = find(u); 
            int pv = find(v);
            if(rank[pu] < rank[pv]){
                root [pu] = pv;
            }else if(rank[pu] > rank[pv]){
                root [pv] = pu;
            }else{
                root [pv] = pu;
                rank [pu]++;
            }
             component--;
        }

        public int find(int u){
            while(u != root[u]){
                root[u] = root[root[u]];
                u = root[u];
            }
            return u;
        } 
    }

    public int makeConnected(int n, int[][] connections) {
        UnionFind uf = new UnionFind(n);
        int redundant = 0;
        for(int [] connection: connections){
            if(!uf.isConnected(connection[0], connection[1])){
                uf.merge(connection[0], connection[1]);
            }else{
                redundant++;
            }
        } 
        
        //System.out.println(uf.component);
        
        int op = (uf.component - 1) - redundant;
        return op > 0 ? -1 : uf.component - 1;
    }
}