并查集

所谓并查集，是图论中比较常见的算法

主要是用来处理合并两个集合或者是询问两个元素是否在同一集合内

也就是合并(merge)和查找(find)

基本原理

每一个集合都是一个树，集合中的每一个元素都用树根来表示，每一个结点存储他的父节点

如何判断树根 f[x] == x

如何获取到某一个元素集合编号while(f[x] != x) x = f[x]

如何合并两个集合 f[x] = y

并查集的简单实现

首先，我们要明确数组的含义，数组内保存的是多种集合的代表元素

我们如何对其进行初始化呢？

因为刚开始没有建立关系，所以我们自己就是代表元素

for(int i = 1;i <= n;i++) {
		f[i] = i;
}

接着我们需要写查找部分

我们如何进行查找呢？

可以分为两种情况，可能出现我就是自己的代表这种情况，这种情况遇到可以直接返回

否则我们应该去搜索代表人，可以通过find(f[x])的方式向上进行搜索

int find(int x) {
		if(f[x] == x) return x;
		else return find(f[x]);
}

最后是合并部分的代码

我们需要知道两个集合的代表是谁，

将其中的一个代表指向另一个代表

void merge(int x,int y) {
		f[find(y)] = find(x); //这种情况相当于将x作为y的新代表
  	//f[find(x)] = find(y); //反之将y作为x的代表，我们可以根据题而议
}

路径压缩

为什么我们需要路径压缩？

举一个例子哈：假如我们初始化只有两个元素1，2 并且1作为代表元素2 –> 1，我们想要更改代表元素为3，那么我们需要将f[1] = 3，接着我们还想修改代表元素为4，即f[3] = 4，循序渐进下去，我们给的元素是2，我们想要查找代表元素，我们需要从2 –> 1 –> 3 –> 4 ……..这么下去很浪费栈，于是我们就需要进行路径压缩

回到正题，如果进行路径压缩？

我们可以将沿途过程中的每一个结点的父结点作为根结点(相当于在查找到的代表和每一个结点之间牵引一根线)，下一次查询就会方便很多

代码修改

int find(int x) {
	if(x == f[x]) return x;
	else return f[x] = find(f[x]);
}

按秩合并

这是一个很简单的合并机制

假如给我们两个集合一个是包含10个元素的集合，还有一个是只有1个元素的集合

我们此时想将两个集合进行合并，我们应该选择将谁合并到谁身上呢？

很显然我们要将少的往多的身上进行合并

如果反之肯能会让树的深度及其结构变得更加的复杂

按秩合并我们需要新建立一个数组rank主要是用来记录集合深度的(其实并不是表示的是具体的深度)

初始化

void initSet(){
		for(int i = 1;i <= n;i++) {
				f[i] = i;
				rank[i] = 1;
		}
}

按秩合并

void merge(int x,int y) {
		int fx = find(x);int fy = find(y);
		if(rank[fx] <= rank[fy]) {
				f[fx] = fy;
		}else {
				f[fy] = fx;
		}
		
		if(fx != fy && rank[fx] == rank[fy]) {
				rank[fy]++;
		}
}