# 1319. Number of Operations to Make Network Connected
###### tags: `Leetcode` `Medium` `Union Find`
Link: https://leetcode.com/problems/number-of-operations-to-make-network-connected/
## 思路
首先检查现在有的connection是不是够把所有的computer连在一起
然后算现在一共有多少个group
我们需要把所有多余的connection挪去把所有的group合并在一起
所以需要挪的connection一共有group-1个
（因为之前检查过connection数量是够的 所以一定有多于group-1个connection是多余的）
## Code

class Solution {
    int[] fa, size;
    int group;
    public int makeConnected(int n, int[][] connections) {
        if(connections.length<n-1) return -1;
        fa = new int[n];
        size = new int[n];
        group = n;
        for(int i=0; i<n; i++){
            fa[i] = i;
            size[i] = 1;
        }
        for(int[] c:connections){
            combine(c[0], c[1]);
        }
        return group-1;
    }
    private int find(int a){
        if(fa[a]==a) return a;
        return fa[a] = find(fa[a]);
    }
    private void combine(int a, int b){
        a = find(a);
        b = find(b);
        if(a==b) return;
        group--;
        if(size[a]>size[b]){
            size[a] += size[b];
            fa[b] = a;
        }
        else{
            size[b] += size[a];
            fa[a] = b;
        }
    }
}