并查集

定义

• 使用father[i]表示i的父节点，当father[i]=i时，i为根节点。同一个集合仅有一个根节点，并将其作为根节点的标识

初始化

//初始化
//for (int i = 0; i < n; i++)
//{
//	father[i] = i;
//}

查找 返回x所在集合的根节点

//查找 返回x所在集合的根节点
int findFather(int x)
{
	while (x != father[x])
	{
		x = father[x];
	}
	return x;
}

合并 如果两个元素不在一个集合，将一个的根节点指向另一个根节点

//合并 如果两个元素在一个集合 没事 否则，将一个的根节点指向另一个根节点
void Union(int a, int b)
{
	int fa = findFather(a), fb = findFather(b);
	if (fa!= fb)
	{
		father[fa] = fb;
	}
}

路径压缩 将路径上所有的结点的父节点都变为根节点

//路径压缩 将路径上所有的结点的父节点都变为根节点
int findFather1(int x)
{
	int fa = findFather(x);
	while (x != father[x])
	{
		int z = father[x];
		father[x] = fa;
		x = z;
	}
	return fa;
}