并查集

摘要

并查集是一种维护集合的数据结构，他的名字中”并”、”查”、”集”分别取自Union、Find、Set三个单词

基本操作

初始化

将自身的父节点指向自己

for(int i=0;i<=N;i++)
	father[i]=i;

查找

findFather(int x)函数返回查找元素的x所在集合的根节点

int findFather(int x){
	while(x!=father[x])//若不是根节点则一直循环
		x=father[x];
	return x;
}

合并

1. 先判断两个节点是否属于同一个集合，若是则无需合并
2. 若不属于一个集合，则将任意一个集合的根节点赋给另外一个集合的根节点

void union(int x,int y){
	int fx = findFather(x);
	int fy = findFather(y);
	if(fx!=fy)
		father[fx]=fy;
}

以上就是并查集的所有操作啦！