并查集

并查集

概念：

并查集是若干个不相交集合，能够实现较快的合并和判断元素所在集合的操作，应用很多。一般采取树形结构来存储并查集。在一些应用问题中，我们需要划分n个不同的元素成若干组，每一组的元素构成一个集合。这种问题的一个解决办法是，在开始时，让每个元素自成一个单元素集合，然后按一定顺序将属于同一组的元素所在的集合合并。其间要反复用到查找一个元素在哪一个集合的运算。

 

 

 

常见两种操作：

将编号分别为1…N的N个对象划分为不相交集合，在每个集合中，选择其中某个元素代表所在集合。

1.合并两个集合

2.查找某元素属于哪个集合

 

进一步优化——路径压缩：

利用一个rank数组来存储集合的深度下界，在查找操作时进行路径压缩使后续的查找操作加速。这样优化实现的并查集，空间复杂度为O(N)，建立一个集合的时间复杂度为O(1)。

思想：

每次查找的时候，如果路径较长，则修改信息，以便下次查找的时候速度更快。

步骤：

1.找到根结点

2.修改查找路径上的所有节点，将它们都指向根结点