https://leetcode-cn.com/problems/connecting-cities-with-minimum-cost/

/* 最小生成树模板 */
class Solution {
    private int f[];    //父节点
    private int w[];    //以i为根的树有多少节点
    private int find(int x) {
        if (f[x] != x) {
            f[x] = find(f[x]);
        }
        return f[x];
    }

    //将所有边从小到大排序
    public int minimumCost(int N, int[][] connections) {
        Arrays.sort(connections, new Comparator<int[]>(){
            @Override
            public int compare(int[] o1, int[] o2) {
                // TODO Auto-generated method stub
                return o1[2] - o2[2];
            }

        });

        int ans = 0;

        f = new int[N + 1];
        w = new int[N + 1];
        for (int i = 1; i <= N; ++i) {
            f[i] = i;
            w[i] = 1;
        }

        for (int e[] : connections) {
            int fa = find(e[0]);
            int fb = find(e[1]);

            if (fa != fb) {
                ans += e[2];
                f[fb] = fa;
                w[fa] += w[fb];
            }
            if (w[fa] == N) {
                return ans;
            }
        }

        return -1;
    }
}