并查集

并查集

并查集是一种采用树形结构存储的集合，可以高效的查找两个元素是否在一个集合当中以及合并两个集合。这里的树形结构并非仅指二叉树，而是一个节点可以有多个孩子。

对于一个并查集的节点，它可以有两个元素，一个存储该节点的数据，另一个用来指向其父节点。当然当我们所存储的元素为1-n的连续整数时，数组下标就可以表征数据，而数组元素存储其父节点下标即可。比如这道题合并集合。

并查集的核心操作就是查找一个元素的根节点，也就是找到该集合中没有父节点的那个节点。由于这个节点在该集合中唯一，且通过该集合中的任意一个节点都可以寻找到该节点，因此一个集合的根节点可以表征这个集合。

如上图，集合1有4个元素[1,2,3,4],集合2有5个元素[5,6,7,8,9]。可以看到，集合1的根节点为值为1的点，集合2的根节点为值为5的点

• 要判断某两个元素是否在一个集合当中，只需要向上找到它们的根节点，若根节点相同，则属于一个集合，反之。
• 若要合并某两个元素所在的集合，也只要找出他们的根节点，由并查集的特性，根节点相同即为同一集合，那么我们只需要将其中一个集合的根节点的父节点设置为另一个集合的根节点即可。

为区分根节点，我们将根节点的父节点值设为-1或者指向自身。

下面给出并查集找根节点的函数，find函数的实现

int find(int u)
{
	while (father[u] != -1) u = father[u];
	//这里使用-1来标记根节点，当然初始化为Father[i] = i ,判断条件为Father[u] != u也可
	return u;
}

find函数实现逻辑很简单，就是迭代的向上找出节点的根节点。

可以看出，find函数查找出根节点的平均时间复杂度跟存储并查集的树的高度或者说层数有关，为O(logn),当极端情况下，每一层仅有一个元素时，查找时间复杂度退化到O(n)。有没有什么方法可以改进呢？
答案是肯定的。我们将find函数中的迭代部分

while(father[u] != -1)u = father[u];
return u;

替换为

if(father[u] != -1) return father[u] = find(father[u]);
else	return u;//找到根节点，返回根节点
//当采用father[i] = i标记时，也可以这样写
if(father[u] != u) father[u] = find(father[u]);
return father[u];

这样的话可以知道，当整个过程递归到最底层时开始返回，而返回的值一直是根节点的下标(两种写法都是)，也就是说，在查找的同时，我们将这个集合的所有节点都连接掉的了根节点上，可以示意为下图

这样的话，原先的多层结构经过一次find操作就变成了一层。因此这样优化之后，find的时间复杂度可以近似为O(1)。这种优化的方法叫做路径压缩