leetcode

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 };