Number of Operations to Make Network Connected

给一个数字n和一个2d数组, 里面是n个数字相连的情况, 问如何调整连接, 让n个数字都相连. 这个题是union-find的经典题. 首先我们知道连接n个node, 至少需要n-1个edge. 然后, 我们做union, 找到有多少个sub components. 把他们都union起来后, 这时需要的edge就是component的数目-1, 因为每个edge都只能连接两个component.

class Solution {
    public int makeConnected(int n, int[][] con) {
        if(con.length < n - 1)
            return -1; // need n-1 edges
        int[] uf = new int[n];
        for(int i = 0 ; i < n; i++)
            uf[i] = i;
        int sub = 0;
        for(int i = 0 ; i < con.length; i++) {
            int first = find(uf, con[i][0]);
            int second = find(uf, con[i][1]);
            uf[first] = second; // union
        }
        for(int i = 0 ; i < n; i++)
            if(uf[i] == i)
                sub++; // sub component 
        return sub - 1;
    }
    
    private int find(int[] uf, int p) {
        if(uf[p] == p)
            return p;
        return find(uf, uf[p]);
    }
}