并查集⚓︎

并查集（ $\text{Disjoint Set Union}，\text{DSU}$ ）是一种用于处理不交集（ $\text{Disjoint Set}$ ）合并及查询问题的数据结构。它支持两种主要操作：

$\text{Find}$ : 查找元素所属的集合，并返回该集合的代表元素（根节点）
$\text{Union}$ : 合并两个元素所属的集合

普通并查集⚓︎

在并查集中，为了提高效率，通常会使用按秩合并和路径压缩这两种优化策略。

按秩合并: 在合并两个集合时，总是将较小的树连接到较大的树上，从而保持树的平衡，减少树的高度
路径压缩: 在执行 $\text{Find}$ 操作时，将访问路径上的所有节点直接连接到根节点，从而加速后续的 $\text{Find}$ 操作

C++

#include <cstdint>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

struct DSU {
  int64_t set_count;  // 当前连通分量数目

  vector<int64_t> root;  // 节点对应的根节点
  vector<int64_t> size;  // 以该节点为根的集合的节点数目

  // 多一个虚拟节点
  explicit DSU(int64_t n) : set_count(n), root(n + 1), size(n + 1, 1) {
    iota(root.begin(), root.end(), 0);
  }

  int64_t Find(int64_t x) { return root[x] == x ? x : root[x] = Find(root[x]); }

  bool Union(int64_t x, int64_t y) {
    x = Find(x);
    y = Find(y);
    if (x == y) { return false; }
    // 按秩合并
    if (size[x] < size[y]) { swap(x, y); }
    root[y]  = x;
    size[x] += size[y];
    --set_count;
    return true;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int64_t n, m;
  cin >> n >> m;
  DSU uf(n);
  for (int64_t i = 0; i < m; ++i) {
    int64_t z, x, y;
    cin >> z >> x >> y;
    if (z == 1) {
      uf.Union(x, y);
    } else {
      cout << (uf.Find(x) == uf.Find(y) ? "Y" : "N") << "\n";
    }
  }
  return 0;
}

扩展域并查集⚓︎

扩展域并查集（ $\text{Extended Disjoint Set Union}$ ）是并查集的一种扩展应用。
当需要处理元素之间存在多种关系（如朋友、敌人、捕食等）时，普通并查集只能处理元素是否属于同一集合的问题，无法满足需求。此时，可以通过扩展元素的表示范围，将一个元素拆分成多个域，每个域代表该元素在不同关系下的状态，从而利用并查集来处理这些复杂关系。

朋友与敌人关系

在处理朋友和敌人关系时，可以将每个元素拆分成两个域：一个表示该元素的朋友集合，另一个表示该元素的敌人集合。
具体实现时，可以将每个元素 $x$ 拆分成两个节点 $x$ 和 $x + n$ ，其中 $n$ 是元素总数。节点 $x$ 代表 $x$ 的朋友集合，节点 $x + n$ 代表 $x$ 的敌人集合。
朋友的朋友是朋友，敌人的敌人是朋友，朋友的敌人是敌人，敌人的朋友是敌人。
当合并两个元素 $x$ 和 $y$ 的朋友关系时，需要同时合并 $x$ 的朋友集合和 $y$ 的朋友集合，以及 $x$ 的敌人集合和 $y$ 的敌人集合。
当合并两个元素 $x$ 和 $y$ 的敌人关系时，需要同时合并 $x$ 的朋友集合和 $y$ 的敌人集合，以及 $x$ 的敌人集合和 $y$ 的朋友集合。
在查询两个元素 $x$ 和 $y$ 的关系时，可以通过检查它们的朋友集合和敌人集合是否在同一个集合中来确定它们是朋友还是敌人。

拓展域并查集的实现和普通并查集相似，只是在合并和查询时需要考虑不同域之间的关系。

食物链

有三类动物 $A,B,C$ ，这三类动物的食物链构成了有趣的环形。 $A$ 吃 $B$ ， $B$ 吃 $C$ ， $C$ 吃 $A$ 。
现有 $N$ 个动物，以 $[1,N]$ 编号。每个动物都是 $A,B,C$ 中的一种，但并不知道具体是哪一种。
现在有 $K$ 条信息，可能是以下两种类型：

$1\ x\ y$ ：表示 $x$ 和 $y$ 是同类
$2\ x\ y$ ：表示 $x$ 吃 $y$

由于信息可能有误，要求计算出其中有多少条是错误的。

C++

#include <cstdint>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

struct DSU {
  int64_t set_count;  // 当前连通分量数目

  vector<int64_t> root;  // 节点对应的根节点
  vector<int64_t> size;  // 以该节点为根的集合的节点数目

  // 多一个虚拟节点
  explicit DSU(int64_t n) : set_count(n), root(n + 1), size(n + 1, 1) {
    iota(root.begin(), root.end(), 0);
  }

  int64_t Find(int64_t x) { return root[x] == x ? x : root[x] = Find(root[x]); }

  bool Union(int64_t x, int64_t y) {
    x = Find(x);
    y = Find(y);
    if (x == y) { return false; }
    // 按秩合并
    if (size[x] < size[y]) { swap(x, y); }
    root[y]  = x;
    size[x] += size[y];
    --set_count;
    return true;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int64_t n, k;
  cin >> n >> k;
  int64_t ans = 0;
  DSU uf(3 * n);
  for (int64_t q = 0; q < k; ++q) {
    int64_t op, i, j;
    cin >> op >> i >> j;
    if (i > n || j > n || op == 2 && i == j) {
      ++ans;
      continue;
    }
    // 将i拆分为i, i+n, i+2n
    // i -> i的同类, i+n -> i的被吃者, i+2n -> i的捕食者
    int64_t xi = i, xi_eat = i + n, xi_pred = i + 2 * n;
    int64_t yj = j, yj_eat = j + n, yj_pred = j + 2 * n;
    if (op == 1) {  // i j是同类
      // 冲突: i的同类是j的被吃者或捕食者
      if (uf.Find(xi) == uf.Find(yj_eat) || uf.Find(xi) == uf.Find(yj_pred)) {
        ++ans;
        continue;
      }
      // 合并同类
      uf.Union(xi, yj);
      uf.Union(xi_eat, yj_eat);
      uf.Union(xi_pred, yj_pred);
    } else {  // op == 2, i 吃 j
      // 冲突: i的同类是j的同类或j的捕食者
      if (uf.Find(xi) == uf.Find(yj) || uf.Find(xi) == uf.Find(yj_pred)) {
        ++ans;
        continue;
      }
      // i的同类是j的被吃者, i的被吃者是j的捕食者, i的捕食者是j的同类
      uf.Union(xi, yj_eat);
      uf.Union(xi_eat, yj_pred);
      uf.Union(xi_pred, yj);
    }
  }
  cout << ans << '\n';
  return 0;
}

带权并查集⚓︎

带权并查集（ $\text{Weighted Disjoint Set Union}$ ）维护的是元素间的数值关系。
常见形式是维护到父节点的权值 $weight[x]$ ，使得能通过与父节点的权值关系回答 $x$ 到 $y$ 的权值关系。
如果只单独给出了一个节点的权重, 考虑能否添加一个虚拟节点,让该节点与虚拟节点之间的权重为该节点的权重。注意该虚拟节点应该始终为根节点。

$\text{Find}$ 操作需要同时更新权值信息， $\text{Union}$ 操作需要调整权值以保持关系正确。

$\text{Find}$ : 在查找根节点的过程中，根据原来的父节点与根节点关系更新路径上每个节点的权值，使其直接指向根节点
$\text{Union}$ : 在合并两个集合时，调整其中一个集合的权值，以保持两个集合之间的数值关系(1)
1. 假设 $weight[y]$ 是 $y$ 到 $root_y$ 的权重, $weight[x]$ 是 $x$ 到 $root_x$ 的权重， $value$ 是 $x$ 到 $y$ 的权重，在距离权重的意义下：
  $root_x$ 到 $root_y$ ( $root_x \rightarrow x \rightarrow y \rightarrow root_y$ )的权重为: $-weight[x]$ + $value$ + $weight[y]$

推导部分和

给定 $M$ 条信息，每条信息包含 $l, r, s$ ，表示区间 $[l, r]$ 的和为 $s$ 。
现在有 $Q$ 个询问，每个询问包含 $l, r$ ，询问区间 $[l, r]$ 的和。
如果无法确定区间和，输出 "UNKNOWN"。

C++

#include <cstdint>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

struct weighted_DSU {
  int64_t set_count;  // 当前连通分量数目

  vector<int64_t> root;    // 节点对应的根节点
  vector<int64_t> weight;  // 相对于父节点的权值

  explicit weighted_DSU(int64_t n) : set_count(n), root(n + 1), weight(n + 1, 0) {
    iota(root.begin(), root.end(), 0);
  }

  // 路径压缩, 修正到根节点的权重
  int64_t Find(int64_t x) {
    // 递归寻找根节点，更新该点到根的权重
    if (x != root[x]) {
      int64_t origin_root = root[x];
      root[x]             = Find(root[x]);
      // 父节点的权重已经更新为到根节点的权重, 更新当前节点的权重
      weight[x] += weight[origin_root];
    }
    return root[x];
  }

  // value表示x到y的权重
  bool Union(int64_t x, int64_t y, int64_t value) {
    int64_t root_x = Find(x), root_y = Find(y);
    if (root_x == root_y) { return false; }
    root[root_x] = root_y;
    --set_count;
    // 更新root_x到root_y的权重
    weight[root_x] = weight[y] - weight[x] + value;
    return true;
  }

  int64_t Query(int64_t x, int64_t y) {
    int64_t root_x = Find(x);
    int64_t root_y = Find(y);
    // 如果两个值有共同的根也就是可以计算，则算结果
    if (root_x == root_y) { return weight[x] - weight[y]; }
    return -1;  // 不在同一个并查集
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int64_t n, m, q;
  cin >> n >> m >> q;
  n += 1;  // 扩展点到 n + 1 (1)
  weighted_DSU wuf(n);
  for (int64_t i = 0; i < m; i++) {
    int64_t l, r, s;
    cin >> l >> r >> s;
    wuf.Union(l, r + 1, s);
  }
  for (int64_t i = 0; i < q; i++) {
    int64_t l, r;
    cin >> l >> r;
    int64_t ans = wuf.Query(l, r + 1);
    if (ans == -1) {
      cout << "UNKNOWN\n";
    } else {
      cout << ans << "\n";
    }
  }
  return 0;
}

Tip
习惯将区间 $[l,r]$ 的和表示为点 $l$ 到点 $r+1$ 的距离。
例如区间 $[1,3]$ 的和为 $5$ ，则表示点 $1$ 到点 $4$ 的距离为 $5$

带权并查集也能处理分类问题（扩展域），只需将权值定义为类别关系即可。

食物链(带权并查集解法)

C++

#include <cstdint>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

struct weighted_DSU {
  int64_t set_count;  // 当前连通分量数目

  vector<int64_t> root;    // 节点对应的根节点
  vector<int64_t> weight;  // 当前节点到父节点的权值

  explicit weighted_DSU(int64_t n) : set_count(n), root(n + 1), weight(n + 1) {
    iota(root.begin(), root.end(), 0);
  }

  int64_t Find(int64_t x) {
    if (x != root[x]) {
      int64_t origin_root = root[x];
      root[x]             = Find(root[x]);
      // 三种关系: 0-同类, 1-吃, 2-被吃
      weight[x] = (weight[x] + weight[origin_root]) % 3;
    }
    return root[x];
  }

  // value表示x到y的权重, 0-同类, 1-吃, 被吃关系隐含为2
  bool Union(int64_t x, int64_t y, int64_t value) {
    int64_t root_x = Find(x), root_y = Find(y);
    if (root_x == root_y) { return false; }
    // 合并x所在集合到y所在集合
    root[root_x] = root_y;
    --set_count;
    // 更新root_x到root_y的权重
    weight[root_x] = (weight[y] - weight[x] + value + 3) % 3;
    return true;
  }

  int64_t Query(int op, int64_t x, int64_t y) {
    int64_t root_x = Find(x);
    int64_t root_y = Find(y);
    // 不在同一个集合
    if (root_x != root_y) { return 1; }
    // x y 是同类, 权重相同
    if (op == 1) { return weight[x] == weight[y] ? 1 : -1; }
    // x 吃 y, 权重差为1
    if (op == 2) { return (weight[x] - weight[y] + 3) % 3 == 1 ? 1 : -1; }
    return 1;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int64_t n, k;
  cin >> n >> k;
  int64_t ans = 0;
  weighted_DSU wuf(n);
  for (int64_t q = 0; q < k; ++q) {
    int64_t op, i, j;
    cin >> op >> i >> j;
    if (i > n || j > n || op == 2 && i == j) {
      ++ans;
      continue;
    }
    int64_t res = wuf.Query(op, i, j);
    if (res == -1) {
      ++ans;
    } else {
      wuf.Union(i, j, op - 1);
    }
  }
  cout << ans << '\n';
  return 0;
}

可撤销并查集⚓︎

可撤销并查集（ $\text{Rollback Union-Find}$ ）是在普通并查集（ $\text{Union-Find / DSU}$ ）的基础上，增加了撤销（ $undo$ ）最近一次合并操作的能力。

在实现时，通常会使用一个栈来记录每次合并操作的状态变化，以便在需要撤销时能够恢复到之前的状态。并且只进行按秩合并，不进行路径压缩，以便于撤销操作的实现。

Ball Collector

给定一棵有 $N$ 个节点的树，节点编号为 $1$ 到 $N$ 。每个节点上有两个球，每个球都有一个编号。从节点 $1$ 到节点 $i$ 的路径上，每个点只能收集一个球，计算每个节点能收集到的不同编号球的最大数量。

Hint

每个球的编号可以看作图中的一个节点，每个树节点提供了连接两个节点的边。设这个连通块包含的节点数为 $s$ ，边数为 $e$ ，如果 $e \lt s$ ，说明这个连通块仍然是树或者森林，新加一条边可以多收集一个不同编号的球；如果 $e \geq s$ ，说明这个连通块已经形成环路，新加一条边不能增加不同编号球的数量。

使用可撤销并查集来处理。在进入一个节点时，合并路径上的球编号集合；在离开节点时，撤销合并操作，恢复到之前的状态。

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <utility>
#include <vector>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  int64_t n;
  cin >> n;
  vector<pair<int64_t, int64_t>> balls(n + 1);
  for (int64_t i = 1; i <= n; i++) { cin >> balls[i].first >> balls[i].second; }
  vector<vector<int64_t>> tree(n + 1);
  for (int64_t i = 1; i < n; i++) {
    int64_t u, v;
    cin >> u >> v;
    tree[u].emplace_back(v);
    tree[v].emplace_back(u);
  }

  vector<int64_t> root(n + 1, 0);
  iota(root.begin(), root.end(), 0);
  vector<int64_t> size(n + 1, 1);        // 记录每个集合的大小
  vector<int64_t> edge_count(n + 1, 0);  // 记录每个集合中的边数
  vector<pair<int64_t, int64_t>> rollback;

  auto find = [&](int64_t x) {
    while (root[x] != x) { x = root[x]; }
    return x;
  };

  auto union_set = [&](int64_t x, int64_t y) {
    int64_t fx = find(x);
    int64_t fy = find(y);
    if (fx == fy) { return; }
    if (size[fx] < size[fy]) { swap(fx, fy); }
    root[fy]        = fx;
    size[fx]       += size[fy];
    edge_count[fx] += edge_count[fy] + 1;
    rollback.emplace_back(fy, fx);
  };

  auto union_rollback = [&]() {
    if (rollback.empty()) { return; }
    auto [fy, fx] = rollback.back();
    rollback.pop_back();
    root[fy]        = fy;
    size[fx]       -= size[fy];
    edge_count[fx] -= edge_count[fy] + 1;
  };

  int64_t count = 0;
  vector<int64_t> answer(n + 1, 0);
  auto dfs = [&](auto &self, int64_t u, int64_t from) -> void {
    int64_t fx = find(balls[u].first);
    int64_t fy = find(balls[u].second);
    bool added = false, merged = false;
    if (fx == fy) {  // 已经在同一集合中
      if (edge_count[fx] < size[fx]) {
        count++;  // 集合中边数小于节点数，可以多选一种球
        added = true;
      }
      edge_count[fx]++;
    } else {  // 不在同一集合中，合并
      if (edge_count[fx] < size[fx] || edge_count[fy] < size[fy]) {
        count++;  // 任一集合中边数小于节点数，可以多选一种球
        added = true;
      }
      union_set(fx, fy);
      merged = true;
    }
    answer[u] = count;
    for (auto &v : tree[u]) {
      if (v == from) { continue; }
      self(self, v, u);
    }
    // 回滚
    if (added) { count--; }
    if (merged) {
      union_rollback();
    } else {
      edge_count[fx]--;
    }
  };
  dfs(dfs, 1, -1);

  for (int64_t i = 2; i <= n; i++) { cout << answer[i] << " "; }
  cout << "\n";

  return 0;
}

Tip

可撤销并查集不进行路径压缩，以便于撤销操作的实现。

可撤销并查集配合分治、树状数组等数据结构，可以高效地处理动态连通性问题。