并查集（Disjoint Set Union，简称DSU，也叫Union-Find）是一种非常精巧的树形数据结构。它的核心用途是高效地处理不相交集合的合并与查询问题。
基本结构
并查集通常用数组（或哈希表）来实现，本质上是维护一个多棵树的森林，其中每棵树代表一个集合。
初始化：一开始，每个元素各自独立成一个集合，自己是自己的“根节点”。用数组parent来记录每个节点的父节点，parent[i] = i 表示 i 是根节点。
查找（Find）—— 追根溯源：给定一个元素 $x$，我们沿着它的父节点链一直向上找，直到找到根节点（即 parent[x] == x 的节点）。
合并（Union）—— 两树相连：要将元素 $x$ 和 $y$ 所在的集合合并，先找到它们的根 rootX 和 rootY。如果根不同，就让其中一个根成为另一个根的父节点（例如 parent[rootX] = rootY）。