划分集合（C++，并查集）

Question

最近遇到了一个难题，有木有人能帮帮我(语言：C++；算法：并查集）
小明拿到了 n 个互不相同的数，他想把这些数分成 A, B 两个集合，每个数都要放进一个集合，对集合里的数有以下要求：

1、如果一个数 x 在集合 A 里， 那么 a - xa−x 也必须在集合 A 里。

2、如果一个数 x 在集合 B 里， 那么 b - xb−x 也必须在集合 B 里。

如果 a - xa−x 不在这 n 个数里，那么 xx 就不能放进集合 AA 里，如果 b - xb−x 不在这 n 个数里，那么 x 就不能放进集合 B 里。
输入格式
第一行包含三个整数 n, a, b（1 ≤ n ≤ 10^5; 1 ≤ a, b ≤ 10^9）
第二行包含 n 个互不相同的整数 P1, p2, P3 ……pn（1 ≤ P[i] ≤ 10^9）

输出格式
如果可以把这 n 个数按要求分成 A, B 两个集合，那么输出两行，第一行输出YES，第二行输出 n 个数，用空格隔开，第 i 个数如果在集合 A 输出 0 ，如果在集合 B 输出 1 。如果有多种划分方案，输出字典序最小的。

如果不能够按要求划分，那么只输出一行，输出NO。

样例1：
输入：
4 5 9
2 3 4 5
输出：
YES
0 0 1 1
样例2：输入：
3 3 4
1 2 4
输出：
NO

Answer 1

不知道你这个问题是否已经解决, 如果还没有解决的话:

• 你可以参考下这个问题的回答, 看看是否对你有帮助, 链接: https://ask.csdn.net/questions/7606772
• 以下回答来自chatgpt:

  解决方案

  首先，我们可以使用并查集来解决这个问题。并查集是一种用来维护一个不相交的集合的数据结构，其中每个集合通过一个代表元素来表示。因此，我们可以将集合A中的某个元素和它的补集（即a-x）表示为同一个集合，将集合B中的某个元素和它的补集（即b-x）表示为同一个集合。如果我们可以将这n个数划分为A和B两个集合，那么这两个集合的代表元素必然是一个在A中，一个在B中。

  接下来，我们可以先将这n个数按从小到大排序，然后遍历排序后的数字。对于每个数字x，我们分别查找a-x和b-x是否在排序后的数组中。如果存在，说明x可以放进集合A或B，我们将其分别对应的集合代表元素更新为x。如果不存在，说明x无法满足条件，我们输出"NO"。

  最后，我们将排序后的数组中的元素按照代表元素的大小分别划分进A和B两个集合，并输出结果。

  以下是具体的代码实现：

  #include <iostream>
  #include <vector>
  #include <algorithm>
  
  using namespace std;
  
  // 并查集
  class DisjointSet {
  private:
      vector<int> parent;  // 保存父节点（代表元素）的索引
  
  public:
      // 初始化并查集
      DisjointSet(int n) {
          parent.resize(n);
          for (int i = 0; i < n; i++) {
              parent[i] = i;  // 初始化每个元素的父节点为自己
          }
      }
  
      // 查找元素x的代表元素
      int find(int x) {
          if (x != parent[x]) {
              parent[x] = find(parent[x]);
          }
          return parent[x];
      }
  
      // 合并两个集合
      void unionSets(int x, int y) {
          int rootX = find(x);
          int rootY = find(y);
          if (rootX != rootY) {
              parent[rootX] = rootY;
          }
      }
  };
  
  // 判断x是否在数组中
  bool exist(const vector<int>& arr, int x) {
      return binary_search(arr.begin(), arr.end(), x);
  }
  
  // 划分集合
  void divideSets(int n, int a, int b, vector<int>& nums) {
      // 排序数组
      sort(nums.begin(), nums.end());
  
      // 初始化并查集
      DisjointSet ds(n);
  
      // 更新集合代表元素
      for (int i = 0; i < n; i++) {
          int x = nums[i];
          int ax = a - x;
          int bx = b - x;
  
          if (exist(nums, ax)) {
              ds.unionSets(i, lower_bound(nums.begin(), nums.end(), ax) - nums.begin());
          }
  
          if (exist(nums, bx)) {
              ds.unionSets(i, lower_bound(nums.begin(), nums.end(), bx) - nums.begin());
          }
      }
  
      // 将集合元素分配到A和B中
      vector<int> setA, setB;
      for (int i = 0; i < n; i++) {
          if (ds.find(i) == i) {
              if (nums[i] > nums[i + 1]) {
                  setB.push_back(nums[i]);
              } else {
                  setA.push_back(nums[i]);
              }
          }
      }
  
      // 输出结果
      if (setA.empty() || setB.empty()) {
          cout << "NO" << endl;
      } else {
          cout << "YES" << endl;
          for (int i = 0; i < n; i++) {
              if (ds.find(i) == i) {
                  if (binary_search(setA.begin(), setA.end(), nums[i])) {
                      cout << "0 ";
                  } else {
                      cout << "1 ";
                  }
              }
          }
          cout << endl;
      }
  }
  
  int main() {
      int n, a, b;
      cin >> n >> a >> b;
      vector<int> nums(n);
      for (int i = 0; i < n; i++) {
          cin >> nums[i];
      }
      divideSets(n, a, b, nums);
      return 0;
  }
  

  通过以上代码，我们可以解决这个关于并查集的问题。如果可以按要求将这n个数划分为集合A和集合B，那么输出"YES"，并输出对应的划分结果（0代表集合A，1代表集合B）。如果无法按要求划分，只输出"NO"。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^