2709. Greatest Common Divisor Traversal #

題目敘述是，在一個陣列中如果一個數字和另一個數字有共同的因數，就可以跳過去。所以可以透過質因數分解每個數字，將同一個數字的所有質因數視為一個群體，最後看連結的群體是否大於一就可以了。

class UnionFind {
public:
    unordered_map<int, int> uf;

    int find(int a) {
        if(!uf.count(a))
            uf[a] = a;
        if(uf[a] != a)
            uf[a] = find(uf[a]);
        return uf[a];
    }
    void merge(int a, int b) {
        uf[find(b)] = find(a);
    }
};
const int primes[65] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 
    53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 
    137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 
    227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313};
class Solution {
public:
    vector<int> factorize(int n) {
        vector<int> facts;
        for (int p : primes)
            if (n % p == 0) {
                facts.push_back(p);
                while(n % p == 0)
                    n /= p;
            }
        if (n != 1) // Some large prime
            facts.push_back(n);
        return facts;
    }
    bool canTraverseAllPairs(vector<int>& nums) {
        if(nums.size() == 1)
            return true;
        int n = nums.size();
        auto uf = UnionFind();
        unordered_set<int> ps;
        unordered_set<int> ns(nums.begin(), nums.end());
        for(int num: ns) {
            if(num == 1)
                return false;
            auto fs = factorize(num);
            for(int f: fs) {
                uf.merge(fs[0], f);
                ps.insert(f);
            }
        }
        unordered_set<int> s;
        for(int key: ps)
            s.insert(uf.find(key));
        return s.size()==1;
    }
};