带阈值的图连通性

/*
思路：
1. 使用并查集（Union-Find）来处理连通性问题。
2. 首先初始化并查集。
3. 遍历所有的数对（x, y），如果它们的公因数 z > threshold，则将它们合并。
4. 对于每个查询，判断两个城市是否在同一个集合中。
使用Java Stream API进行处理。
*/

import java.util.stream.IntStream;

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

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

        public int find(int x) {
            if (parent[x] != 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[] areConnected(int n, int threshold, int[][] queries) {
        UnionFind uf = new UnionFind(n);

        IntStream.range(threshold + 1, n + 1).forEach(i -> {
            IntStream.iterate(2 * i, j -> j <= n, j -> j + i).forEach(j -> uf.union(i, j));
        });

        return IntStream.range(0, queries.length)
            .mapToObj(i -> uf.find(queries[i][0]) == uf.find(queries[i][1]))
            .mapToBoolean(Boolean::booleanValue)
            .toArray();
    }
}