并查集是一种动态维护多个不重复集合

在并查集中，每个集合都有自己的代表元素。

一个树 $ fa $ 记录每一个元素的归属关系（存储所属集合代表元素的下标）。

具体：

初始状态：

即，每个元素都是一个单独的集合

int fa[10009];
for (int i = 0; i < n; i++) fa[i] = i;

常见操作

Get

查询一个元素属于哪一个集合（通常题目中会问两个元素是否属于同一集合）

int find(int x) {
    if (fa[x] == x) return x;
    return find(fa[x]);
}