Leetcode 2709. Greatest Common Divisor Traversal

[Woodyiiiiiii]

2709. Greatest Common Divisor Traversal

2709. Greatest Common Divisor Traversal

类似题目：

• 952. Largest Component Size by Common Factor
• 2709. Greatest Common Divisor Traversal

这道题我在竞赛时有思路，但没理顺，还一度放弃了正解。所以要在比赛中梳理好思路。

显然这题是素数筛+并查集。素数筛是为了处理10^6大小的元素的。

接着，如何让各个元素之间联系起来呢？自然而然想到并查集。但并查集的连接union方法该如何使用呢？

我总结的是，“缓存”有两种使用方式：第一种是先过一遍缓存，再过第二遍；第二种是边遍历边记录。这里是第二种，可以要用哈希表存储质因数和节点的一一对应关系。

class Solution {
    Map<Integer, Set<Integer>> memo = new HashMap<>();

    public boolean canTraverseAllPairs(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return true;
        }
        UnionSet unionSet = new UnionSet(n);
        Map<Integer, Integer> p2IdxMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            Set<Integer> primes = primeFactorization(num);
            for (int p : primes) {
                if (p2IdxMap.containsKey(p)) {
                    unionSet.union(p2IdxMap.get(p), i);
                } else {
                    p2IdxMap.put(p, i);
                }
            }
        }
        // determine if there is rank == n
        for (int i = 0; i < n; i++) {
            if (unionSet.rank[i] == n) {
                return true;
            }
        }
        return false;
    }

    // prime factorization
    public Set<Integer> primeFactorization(int n) {
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        int t = n;
        Set<Integer> ans = new HashSet<>();
        for (int i = 2; i * i <= n; i++){
            while (n % i == 0){
                ans.add(i);
                n /= i;
            }
        }
        if (n > 1) {
            ans.add(n);
        }
        memo.put(t, ans);
        return ans;
    }

    class UnionSet {
        int n;
        int[] f;
        int[] rank;

        public UnionSet(int n) {
            this.n = n;
            f = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) {
                f[i] = i;
                rank[i] = 1;
            }
        }

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

        public void union(int x, int y) {
            int fx = find(x);
            int fy = find(y);
            if (fx == fy) {
                return;
            }
            f[fx] = fy;
            rank[fy] += rank[fx];
        }
    }
}