并查集（union-find） 介绍 概念 当涉及到处理元素之间的等价关系、集合的合并与查询等问题时，它是一种用于维护不相交集合的有效方法，常被用于解决诸如连通性、网络连接状态、等价关系等问题。 核心思想 并查集通过构建一个森林（或者称为集合），其中每个元素都属于一个集合，每个集合以一个代表元素来标识。这样的数据结构可以高效地进行两个关键操作：查找和合并。 操作 查找（Find）： 查找一个元素所属的集合，通常以代表元素作为标识。这个操作通常用于判断两个元素是否属于同一个集合，即判断它们的代表元素是否相同。 123int find(int x) { return pa[x] == x ? x : (pa[x] = find(pa[x]));} 合并（Union）： 将两个不相交的集合合并为一个集合，即将两个集合的代表元素连接在一起。 1234567void union(int x, int y) { int fx = find(x), fy = find(y); if (fx == fy) return; if (rank[ ...