5866. 数组的最大公因数排序

5866. 数组的最大公因数排序

并查集 ，预处理

const int N = 1e5 + 10;

class Solution {
 public:
  int p[N];
  int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
  }
  void merge(int a, int b) {
    int ra = find(a), rb = find(b);
    p[ra] = rb;
  }
  bool gcdSort(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < N; i++) p[i] = i;
    for (int i = 0; i < nums.size(); i++) {
      int x = nums[i];
      for (int j = 2; j * j <= x; j++) {
        bool flag = false;
        while (x % j == 0) {
          x /= j;
          flag = true;
        }
        if (flag) merge(j, nums[i]);
      }
      if (x > 1) merge(x, nums[i]);
    }

    vector<int> arr = nums;
    sort(arr.begin(), arr.end());

    for (int i = 0; i < n; i++) {
      if (find(arr[i]) != find(nums[i])) return false;
    }
    return true;
  }
};