【数据结构基础C++】并查集（Disjoint Set or Union-Find)）

并查集是一种树形的数据结构，用于处理一些不相交集合的合并（Union）及查询问题（Find）。
可以用一个1维数组进行跟踪。父亲数组 parent[ ]，记录节点的父亲节点是谁。初始化节点父亲为自己本身，两两节点互不连接。
考虑如下图：

Find： 不断查询自己的父亲节点，直到到达根节点。根节点为 parent[i] == i;

int find(int i){
	while(i != parent[i]){
		i = parent[i];
	}
	return i;
}

Union： 合并节点 x 和节点 y 所属的集合；先用find函数找到 节点 x 的根节点和节点 y 的根节点；若他们不属于同一个根节点，则进行连接（合并）。

void Union(int x,int y){
	int rootX = find(x);
	int rootY = find(y);
	if(rootX == rootY)
		return;
	parent[rootX] = rootY;
}

bool isConnected(int x,int y){
	return find(x) == find(y);
}

在Uion函数中，总是将第一个元素的根节点指向第二个元素的根节点 parent[rootX] = rootY，在这种情况下，会出现树越来越高，查找时间增加。

要解决这个问题，就不应该固定的将一个元素的根节点指向另外一个根节点，可以在连接操作之前，进行一个判断，可以存储每一个集合具体有多少个节点。在Union操作时，将节点少的那组集合的根节点指向节点多的集合的根节点。这样可以大概率形成一棵层数较少的树。
可以用一个数组表示集合中的节点个数：

//sz[i] 表示以i为根的结合中的元素个数
int* sz；

初始化sz数组时，数组值都为1，因为一开始所有节点互相独立，都以自己为根。
优化Union函数：

void Union(int x,int y){
	int rootX = find(x);
	int rootY = find(y);
	if(rootX == rootY)
		return;
	//若以rootX为根的集合中的节点个数 小于 以rootY为根的集合中的节点个数，则用少的指向多的
	if(sz[rootX] < sz[rootY]){
		parent[rootX] = rootY;
		//由于rootX指向了rootY，相应的以rootY为根的集合中的节点个数增加了
		sz[rootY] += sz[rootX];	
	}
	else{
		parent[rootY] = rootX;
		sz[rootX] += sz[rootY];	
	}	
}

我们希望将层数低的子集union到层数高的子集中。rank[i] 表示根节点为 i 的树的高度。如下图，想Union（1,5），若按照上一个根据集合中个数，将少的连接到多的，合并后树的高度为5；若按照树的层高优化，将层数低的并到层数，合并后树的高度为4；



可以用一个rank数组记录根节点的树高

//rank[i] 表示以i节点为根的树的树高
int* rank;

优化Union函数：

void Union(int x,int y){
	int rootX = find(x);
	int rootY = find(y);
	if(rootX == rootY)
		return;
	//若以rootX为根的层高 小于 以rootY为根的层高，则用层高低的指向层高高的
	if(rank[rootX] < rank[rootY]){
		parent[rootX] = rootY;	
		//rank[rootY]不变
	}
	else if(rank[rootY] < rank[rootX]){
		parent[rootY] = rootX;
	}
	else{
	//在树高相等的情况下，谁指向谁都可以，维护rank的值，树的层高+1
		parent[rootX] = rootY;	
		sz[rootY] += 1;
	}	
}

在find函数中，为了找到节点所属的根节点，几乎遍历了所有节点。可以尝试在find函数中，从底向上，若没有找到根的话，就将该结点的父节点的父节点作为该结点的父节点。
如下图：要找节点1 的根节点：

parent[1] != 1; 将parent[1] = parent[parent[1]] = 3;

接着考察节点1的父亲节点3，parent[3] != 3;将parent[3] = parent[parent[3]] = 4;

优化代码：

int find(int i){
	while(i != parent[i]){
		parent[i] = parent[parent[i]];
		i = parent[i];
	}
	return i;
}