并查集

简单版本

void solve() {
  int n, m;
  cin >> n >> m;
  vector<int> fa(n + 1);

  // init
  iota(fa.begin(), fa.end(), 0);

  // 找父亲
  function<int(int)> find = [&](int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
  };

  // 合并
  auto merge = [&](int x, int y) {
    fa[find(x)] = find(y);
  };

  while (m--) {
    int q, x, y;
    cin >> q >> x >> y;
    if (q == 1) {
      merge(x, y);
    } else {
      cout << ((find(x) == find(y)) ? "Y" : "N") << endl;
    }
  }
}

启发式合并

void solve() {
  int n, m;
  cin >> n >> m;
  vector<int> fa(n + 1), sz(n + 1, 1);
  iota(fa.begin(), fa.end(), 0);

  // 找父亲
  function<int(int)> find = [&](int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
  };

  // 启发式合并
  auto merge = [&](int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) {
      return;
    }
    if (sz[fx] < sz[fy]) {
      swap(fx, fy);
    }
    fa[fy] = fx;
    sz[x] += sz[y];
  };

  while (m--) {
    int q, x, y;
    cin >> q >> x >> y;
    if (q == 1) {
      merge(x, y);
    } else {
      cout << ((find(x) == find(y)) ? "Y" : "N") << endl;
    }
  }
}

删除与移动

删除：将父亲设为自己，为了保证删除的元素都是叶节点，设置副本并初始化父亲为副本。 移动：保重移动的元素都在叶子节点。

实现以下功能：

1. 合并两个元素所处集合。
2. 移动 $p$ 到 $q$ 集合。
3. 查询元素所在集合大小和元素和。

void solve() {
  int n, m;
  if (!(cin >> n >> m)) {
    exit(0);
  }
  vector<int> fa((n + 1) * 2), sz((n + 1) * 2, 1);
  vector<int> su((n + 1) * 2); // 添加统计大小

  // 初始化
  iota(fa.begin(), fa.begin() + n + 1, n + 1);
  iota(fa.begin() + n + 1, fa.end(), n + 1);
  iota(su.begin() + n + 1, su.end(), 0);

  // 找父亲
  function<int(int)> find = [&](int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
  };

  // 启发式合并（按大小）
  auto merge = [&](int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) {
      return;
    }
    if (sz[fx] < sz[fy]) {
      swap(fx, fy);
    }
    fa[fy] = fx;
    sz[fx] += sz[fy];
    su[fx] += su[fy];
  };

  // 删除
  auto remove = [&](int x) {
    --sz[find(x)];
    fa[x] = x;
  };

  // 移动
  auto move = [&](int x, int y) {
    auto fx = find(x), fy = find(y);
    if (fx == fy) {
      return;
    }
    fa[x] = fy;
    --sz[fx], ++sz[fy];
    su[fx] -= x, su[fy] += x;
  };

  while (m--) {
    int q;
    cin >> q;
    if (q == 1) {
      int x, y;
      cin >> x >> y;
      merge(x, y);
    } else if (q == 2) {
      int x, y;
      cin >> x >> y;
      move(x, y);
    } else if (q == 3) {
      int x;
      cin >> x;
      int fx = find(x);
      cout << sz[fx] << ' ' << su[fx] << endl;
    }
  }
}