unionfind

并查集（union-find）

在计算机科学中，并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。有一个联合-查找算法（union-find algorithm）定义了两个用于此数据结构的操作：

• Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
• Union：将两个子集合并成同一个集合。

动态连通性

假设输入是一列整数对，其中每个整数都表示某种类型的对象。输入的的整数对是p和q，我们可以理解p和q是相连的。也就意味着具有三个特性：

• 自反性：p和q是相连的；
• 对称性：如果p和q是相连的，那么q和p也是相连的；
• 传递性：如果p和q是相连的并且q和是相连的，那么p和r也是相连的。