并查集在处理哪些数据结构问题时特别有效？

本文共计1105个文字，预计阅读时间需要5分钟。

集合查询，关注意义，便是合并、查找集合：对于集合S={a1, a2, ..., an-1, an}，我们还可以对集合S进行一步划分：S1, S2, ..., Sm-1, Sm。我们希望能够快速确定S中的两个元素是否属于同一子集。

并查集，顾名思义，就是合并、查找集合：

对于一个集合S={a1, a2, ..., an-1, an}，我们还可以对集合S进一步划分: S1,S2,...,Sm-1,Sm。我们希望能够快速确定S中的两两元素是否属于S的同一子集。

主要是两个操作：

1、Find：查找元素所属集合

2、Union：合并两个集合成一个新的集合

基本解析：

可以用树来表示这种数据结构——集合。最初的时候每一个元素都是一个集合 。

那如果我们现在想把{0}和{1}合并成一个集合{0，1}该怎么办呢？那就要自定义并使用Union函数（具体代码实现下文会提及）

然而如果我想判断两个元素是否在同一个集合中，就可以用Find函数来实现

代码思想：

首先定义一个parent数组来表示元素的父结点。