2709.cpp (2039B)
1 class UnionFind { 2 int n, cnt = n; 3 mutable vector<int> root; 4 vector<int> size; 5 6 public: 7 UnionFind(int n) : n(n), root(n), size(n, 1) { iota(root.begin(), root.end(), 0); } 8 UnionFind(const UnionFind &uf) : n(uf.n), cnt(uf.cnt), root(uf.root), size(uf.size) {} 9 10 int find(int x) const { 11 while (x != root[x]) { 12 x = root[x] = root[root[x]]; 13 } 14 return x; 15 } 16 17 void join(int x, int y) { 18 x = find(x), y = find(y); 19 if (x == y) return; 20 21 if (size[x] > size[y]) swap(x, y); 22 root[x] = y; 23 size[y] += size[x]; 24 cnt--; 25 } 26 27 bool connected(int x, int y) const { return find(x) == find(y); } 28 29 void reset() { 30 memset(size.data(), 0x00, size.size() * sizeof(int)); 31 iota(begin(root), end(root), 0); 32 } 33 }; 34 35 class Solution { 36 static constexpr const int maxi = 100001; 37 typedef array<int, maxi> cache_t; 38 39 public: 40 bool canTraverseAllPairs(const vector<int> &nums) const { 41 const int n = size(nums); 42 static UnionFind uf(2 * maxi + 1); 43 uf.reset(); 44 45 if (n == 1) return true; 46 47 static cache_t cache = {{0}}; 48 if (!cache[2]) { 49 for (int i = 2; i < size(cache); i++) { 50 if (cache[i]) continue; 51 for (int j = i; j < size(cache); j += i) { 52 cache[j] = i; 53 } 54 } 55 } 56 57 static char seen[maxi]; 58 memset(seen, 0x00, sizeof(seen)); 59 60 for (int i = 0; i < n; i++) { 61 if (nums[i] == 1) return false; 62 seen[nums[i]] = 1; 63 for (int val = nums[i]; val > 1;) { 64 const int prime = cache[val]; 65 const int root = prime + maxi; 66 uf.join(root, nums[i]); 67 while (val % prime == 0) 68 val /= prime; 69 } 70 } 71 72 int count = 0; 73 for (int i = 0; i < maxi; i++) 74 count += seen[i] && i == uf.find(i); 75 return count == 1; 76 } 77 };