并查集

并查集（Union Find）是一种用于维护集合的数据结构。它支持快速的合并（Union）和查找（Find）操作，可以用于解决一些图论、网络和数据结构等领域的问题。并查集通常用于判定图中的连通性，或者用于维护集合的分组，例如在图像分割、聚类等领域。

并查集的基本思想是维护一些集合，每个集合有一个代表元素，可以用一个数组来记录每个元素属于哪个集合。在合并两个集合时，只需要将其中一个集合的代表元素指向另一个集合的代表元素即可。在查找元素所属集合时，只需要沿着代表元素一直向上查找，直到找到根节点。

并查集的时间复杂度主要取决于集合的合并和查找操作的时间复杂度。如果使用路径压缩和按秩合并等优化技巧，可以将每个操作的时间复杂度降到近似于常数级别。