连通网络的操作次数

/*
 * 题目思路：
 * 与上题思路相同，使用并查集解决问题。但这次利用Java Stream来优化代码的可读性和简洁性。
 */

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

public class SolutionStream {
    public int makeConnected(int n, int[][] connections) {
        if (connections.length < n - 1) return -1; // 不足够连接所有计算机

        UnionFind uf = new UnionFind(n);
        long extraEdges = Arrays.stream(connections)
                                .filter(conn -> !uf.union(conn[0], conn[1]))
                                .count(); // 记录多余的连接

        return uf.components - 1 <= extraEdges ? uf.components - 1 : -1;
    }

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

        public UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            components = n;
            IntStream.range(0, n).forEach(i -> parent[i] = i);
        }

        public int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]); // 路径压缩
            }
            return parent[x];
        }

        public boolean union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) return false;

            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }

            components--;
            return true;
        }
    }
}