夺回据点

/*
 * 思路：
 * 1. 找出最低成本的据点作为初始夺回的据点。
 * 2. 使用一个并查集（Union-Find）结构来维护已夺回和未夺回据点的连通性。
 * 3. 从最小花费开始尝试夺回据点，确保每次夺回据点后，剩余的魔物据点依然连通。
 */

import java.util.*;
import java.util.stream.Collectors;

public class Solution {
    public int minCost(int[] cost, int[][] roads) {
        int n = cost.length;
        UnionFind uf = new UnionFind(n);
        List<int[]> edges = Arrays.stream(roads)
                                   .sorted(Comparator.comparingInt(o -> Math.min(cost[o[0]], cost[o[1]])))
                                   .collect(Collectors.toList());
        int minCost = Integer.MAX_VALUE;
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            if (!uf.connected(u, v)) {
                uf.union(u, v);
                minCost = Math.min(minCost, cost[u] + cost[v]);
            }
        }
        return minCost;
    }

    class UnionFind {
        private int[] parent;
        private int[] rank;

        public UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                rank[i] = 1;
            }
        }

        public int find(int x) {
            if (x != parent[x]) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX != rootY) {
                if (rank[rootX] > rank[rootY]) {
                    parent[rootY] = rootX;
                } else if (rank[rootX] < rank[rootY]) {
                    parent[rootX] = rootY;
                } else {
                    parent[rootY] = rootX;
                    rank[rootX]++;
                }
            }
        }

        public boolean connected(int x, int y) {
            return find(x) == find(y);
        }
    }
}