最低成本连通所有城市

/*
 * 思路：
 * 1. 使用Kruskal算法来找到最小生成树（Minimum Spanning Tree, MST），从而找到连通所有城市的最低成本。
 * 2. 首先将所有的边按照权重进行排序。
 * 3. 使用并查集（Union-Find）来检测是否会形成环，并构建最小生成树。
 * 4. 使用Java Stream API来处理集合和数组操作。
 */
import java.util.*;
import java.util.stream.*;

public class Solution {
    class Edge implements Comparable<Edge> {
        int city1, city2, cost;
        public Edge(int city1, int city2, int cost) {
            this.city1 = city1;
            this.city2 = city2;
            this.cost = cost;
        }
        public int compareTo(Edge other) {
            return this.cost - other.cost;
        }
    }

    public int minimumCost(int n, int[][] connections) {
        List<Edge> edges = Arrays.stream(connections)
            .map(conn -> new Edge(conn[0] - 1, conn[1] - 1, conn[2]))
            .sorted()
            .collect(Collectors.toList());
        UnionFind uf = new UnionFind(n);
        int totalCost = edges.stream()
            .filter(edge -> uf.union(edge.city1, edge.city2))
            .mapToInt(edge -> edge.cost)
            .sum();
        return uf.getCount() == n - 1 ? totalCost : -1;
    }

    class UnionFind {
        private int[] parent, rank;
        private int count;
        public UnionFind(int size) {
            parent = new int[size];
            rank = new int[size];
            count = 0;
            for (int i = 0; i < size; i++) {
                parent[i] = i;
                rank[i] = 1;
            }
        }
        public int find(int p) {
            if (parent[p] != p) {
                parent[p] = find(parent[p]);
            }
            return parent[p];
        }
        public boolean union(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP == rootQ) return false;
            if (rank[rootP] > rank[rootQ]) {
                parent[rootQ] = rootP;
            } else if (rank[rootP] < rank[rootQ]) {
                parent[rootP] = rootQ;
            } else {
                parent[rootQ] = rootP;
                rank[rootP]++;
            }
            count++;
            return true;
        }
        public int getCount() {
            return count;
        }
    }
}