简介

一种用于管理元素所属集合的数据结构。

大致思想

用一个森林，以根元素区分所属集合。

一般进行两种操作: 合并和查询。

例题

【模板】并查集

模板代码

int n;
std::vector<int> set(n);
auto find = [&](auto &find, int x) -> int {
  if(set[x] == x) return x;
  return find(find, set[x]);
};