并查集详解：数学语言描述及操作公式 - 数据结构

并查集是一种用于处理不相交集合的合并及查询问题的数据结构。它支持两种基本操作：

1. 合并操作: 将两个集合合并成一个集合。
2. 查询操作: 判断两个元素是否属于同一个集合。

数学表示:

假设 X 表示所有元素的集合，并查集可以表示为一个由若干个集合构成的集族：

X = {S1, S2, ..., Sn}

其中 Si 表示第 i 个集合，其代表元素为 pi。

每个集合 Si 可以进一步表示为包含若干个元素：

Si = {e1, e2, ..., ek}

其中 ei 表示第 i 个元素，k 为 Si 中元素的个数。每个元素 ei 都有一个父节点 pi，用 pi 表示 ei 所在集合的代表元素。如果 ei 是自己的代表元素，则 pi = ei。

路径压缩优化:

并查集有一个重要的性质，即路径压缩。在进行查询操作时，将路径上的所有节点都直接连接到代表元素上，可以减少查询操作的时间复杂度。

操作公式:

1. 合并操作:

merge(Si, Sj) -> Sk

其中 Si 和 Sj 是要合并的两个集合，Sk 是合并后的集合。

2. 查询操作:

find(ei) -> pi

其中 ei 是要查询的元素，pi 是 ei 所在集合的代表元素。

通过这些数学公式和描述，可以更深入地理解并查集的概念和操作，并为实际应用提供理论基础。