并查集

并查集

并查集是一种树形结构，又叫“不相交集合”，保持了一组不相交的动态集合，每个集合通过一个代表来识别，代表即集合中的某个成员，通常选择根做这个代表。

并查集作用

• 并查集主要用于解决分组问题，它用来管理一系列不想交的集合，支持如下两种操作：
  • 合并：把两个不相交的集合合并为一个集合
  • 查询：查询某个元素的根节点，可以判断两个元素的根节点是否相等判断两个元素是否在一个并查集中。

并查集三种主要操作

• Make_Set(x):
  • 建立一个新的集合，其唯一成员就是x，因此这个集合的代表也是x，并查集要求各集合是不相交的，因此要求x没有在其他集合中出现过。
• Find_Set(x):
  • 返回能代表x所在集合的节点，通常返回x所在集合的根节点。有递归和非递归两种方法，下面会有讲解。
• Union(x, y):
  • 将包含x,y的动态集合合并为一个新的集合。合并两个集合的关键是找到两个集合的根节点，如果两个根节点相同则不用合并；如果不同，则需要合并。

并查集优化

• Union(x, y)时按秩合并
  合并时，如果两个集合的秩相同，任选一个根做为父节点，并增加其秩。
  秩不同时，让较小秩的集合指向较大秩的集合，这时秩的大小不变。
  秩和集合的数目是不一样的，秩表示节点高度的一个商界；集合的数目表示集合中节点的总数。

• Find_Set(x)路径压缩
  在Find_Set(x)中，是查找路径上的每个节点都直接指向根节点，这样下次再找根节点的时间复杂度会变成o(1)