并查集讲解

并查集

顾名思义，对集合进行合并和查找操作。
合并：将两个集合或元素合并成一个。
查找：查找两个元素是否在同一集合中。
实现：通过建立一个father数组，即一个父亲节点 数组，记录这一个节点的父亲节点，并且父亲节点也在此集合内。
！！！同一集合中只存在一个根结点，这个根结点是这个集合中所有元素的根结点，是整个集合的编号。

模板step:
1.初始化
一开始所有节点都是独立的，那么就要将其父亲节点设置为他们自己来表明自身是独立的。

for(int i=0;i<n;i++)
{
		father[i]=i;
}
1
2
3
4

2.查找
一个集合必须要有一个根结点来表示，那么我们可以通过递归不断查找父亲节点。从而找到根结点老祖宗。

int find(int x)
{
	if(father[x]==x)
	{
	//如果我是老祖宗那么就返回祖宗节点
		return x;
	}
	else
	{
	//如果我不是，那就判断我爸爸是不是
	return find(father[x]);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

3.合并
将两个集合合并成一个集合，只有属于两个不同集合的元素才能合并，分两步
step1：判断两个人是不是一个集合的(是不是一个老祖宗)
step2：如果不是那么进行合并操作

void Union(int a,int b)
{
	int fathera=find(a);//查找a的祖宗
	int fatherb=find(b);//查找b的祖宗
	if(fathera!=fatherb){
	fa[fatherb]=fathera;
	}
}
1
2
3
4
5
6
7
8

!!!不能简单地将这个元素的父亲设为另一个元素，是fa[fatherb]=fathera;而不是fa[b]=fathera;

优化

int find(int x){
    if(father[x]==x){
        return x;
    }
    else{
        return father[x]=find(father[x]);
        //直接将根结点赋值为当前节点的父亲节点。
    }
}
1
2
3
4
5
6
7
8
9

借鉴这位小姐姐的博客，直通车~