按公因数计算最大组件大小

/*
题目思路：
1. 我们需要找到图中最大的连通组件的大小，图中的节点由数组nums中的元素表示，
   如果两个元素有一个大于1的公因数，那么它们之间有一条边。
2. 为了求解，我们可以使用并查集（Union-Find）来跟踪每个节点所属的连通分量。
3. 对于每个数，我们找到它的所有因数，并将这些因数所在的集合进行合并。
4. 最终，我们通过查找每个集合的大小来确定最大的连通组件的大小。
*/

import java.util.*;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class LargestComponentSizeStream {
    public int largestComponentSize(int[] nums) {
        int max = Arrays.stream(nums).max().orElse(0);
        UnionFind uf = new UnionFind(max + 1);

        Arrays.stream(nums).forEach(num -> {
            IntStream.rangeClosed(2, (int) Math.sqrt(num)).filter(factor -> num % factor == 0).forEach(factor -> {
                uf.union(num, factor);
                uf.union(num, num / factor);
            });
        });

        Map<Integer, Long> count = Arrays.stream(nums).boxed()
            .collect(Collectors.groupingBy(uf::find, Collectors.counting()));

        return count.values().stream().max(Long::compareTo).orElse(0L).intValue();
    }

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

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

        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]++;
                }
            }
        }
    }
}