leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

2709.cpp (2039B)

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