1135.最低成本联通所有城市

1135. 最低成本联通所有城市

难度中等49

想象一下你是个城市基建规划者，地图上有 N 座城市，它们按以 1 到 N 的次序编号。

给你一些可连接的选项 conections，其中每个选项 conections[i] = [city1, city2, cost] 表示将城市 city1 和城市 city2 连接所要的成本。（连接是双向的，也就是说城市 city1 和城市 city2 相连也同样意味着城市 city2 和城市 city1 相连）。

返回使得每对城市间都存在将它们连接在一起的连通路径（可能长度为 1 的）最小成本。该最小成本应该是所用全部连接代价的综合。如果根据已知条件无法完成该项任务，则请你返回 -1。

示例 1：

image

输入：N = 3, conections = [[1,2,5],[1,3,6],[2,3,1]]
输出：6
解释：
选出任意 2 条边都可以连接所有城市，我们从中选取成本最小的 2 条。</pre>

class Solution {
    public int minimumCost(int N, int[][] connections) {
        // 排序，然后按照值小的往值大的里加；直到连通;
        // 如果最后都没有连通，则return -1;
        // 如果最后出现多余的边，find的两端的祖先一样，那么说明这条边用不上。跳过这条边;
        Arrays.sort(connections,(o1,o2)->(o1[2]-o2[2]));
        UnionFind uf = new UnionFind(N);
        int res = 0;
        for(int i=0;i<connections.length;i++){
            if(uf.union(connections[i][0],connections[i][1])){
                res += connections[i][2];
            }
        }
        if(uf.size>1){
            return -1;
        }
        return res;
    }


    public class UnionFind{
        Map<Integer,Integer> fatherMap;
        Map<Integer,Integer> sizeMap;
        int size;
        // 初始化;
        public UnionFind(int N){
            fatherMap = new HashMap();
            sizeMap = new HashMap();
            for(int i=1;i<=N;i++){
                fatherMap.put(i,i);
                sizeMap.put(i,1);
            }
            size = N;
        }

        // FindFather
        public int Find(int key){
            int t = fatherMap.get(key);
            if(t==key){return t;}
            int b = Find(t);
            // 把并查集变扁平：
            fatherMap.put(key,b);
            return b;
        }

        // Union
        public boolean union(int a,int b){
            int aFather = Find(a);
            int bFather = Find(b);
            //
            if(aFather==bFather){return false;}//不用union，本来就是一家人;
            if(sizeMap.get(aFather)>sizeMap.get(bFather)){
                // a的父变成b的父;
                fatherMap.put(bFather,aFather);
                sizeMap.put(aFather,sizeMap.get(aFather)+sizeMap.get(bFather));
            }else{
                fatherMap.put(aFather,bFather);
                sizeMap.put(bFather,sizeMap.get(aFather)+sizeMap.get(bFather));
            }
            size--;
            return true;
        }
    }
}