数据结构-并查集

并查集是维护集合的数据结构 它支持合并(Union) 查找(Find)功能
首先需要一个father数组(int father[N])存放父亲结点
father[i]表示元素i 的结点的父亲结点
例如 father[1] = 2;表示结点1的父亲结点是2；
在并查集初始化的时候father[i] = i;表示一开始自己的父亲是自己(核心)
为什么这么初始化,下面你会慢慢了解

//初始化
const int N = 1001;
int father[N];
void init(){ 
    for(int i=0;i<N;i++) father[i] = i;
}

并查集其实是一颗多叉树，树中只有一个根节点(即该结点是所有孩子的最终父亲结点)，什么是最终的父亲结点，其实很简单,比如father[1] = 2,father[2] = 3,father[3] = 3;这个时候假如求1的最终父亲结点,首先通过father[1] = 2,找到1号结点的父亲结点是2,接下来，再一次找,通过father[2] = 3;此时我们找到2号结点的父亲结点是3,这时候，通过father[3] = 3,找3结点的父亲结点是3,这个是本身,说明自己的父亲是自己(知道为甚一开始初始化了吧)，此时的3就就最终父亲结点。话不多说,咱们上代码,代码怎么写呢，好像要一层层的找过去,是不是很像递归函数。。。。
但是，这样确实可以找到最终父亲结点，但是当数据量很大时候,每次都要重新找,是不是时间会超时，如果你懂记忆化搜索的dfs，你就会知道，这里可以用路径压缩来写,不懂也没有事,咱们慢慢学,那么什么是路径压缩，在之前我提过,并查集其实把一个个连通块(不要被连通块这个名词吓怕,连通块就是这些点之前都能够到达,它们在一个集合里面)合起来,它是一颗多叉树,每次查询时候,我们只要找到他的最终父亲结点，所以我们可以直接把自己父亲结点改为根节点(最终结点)，是不是就行了，话不多说，上代码。。。

int find_father(int x){ 
	if(father[x]==x){ //递归出口
		return x;
	}
	else{ 
		int temp = find_father(father[x]);
	    father[x] = temp;//路径压缩
	    return temp;
	}
}

下一个环节是并操作（Union）

void Union(int u,int v){ 
	int fu = find_father(u);//找u结点的最终父亲结点
	int fv = find_father(v);//找v结点的最终父亲结点
	if(fu!=fv){ //如果两个连通块不在一个集合,这个时候实施并操作,只要把一个结点作为父亲即可
		father[fu] = fv;
	}
}

看一道题目
链接:https://www.luogu.com.cn/problem/P3367

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000001;
int father[maxn];
void init(int n){ 
	for(int i=1;i<=n;i++) father[i] = i;
}
int find_father(int x){ 
	if(x==father[x]) return x;
	int temp = find_father(father[x]);
	father[x] = temp;
	return temp;
}
void Union(int u,int v){ 
	int fu = find_father(u);
	int fv = find_father(v);
	if(fu!=fv) father[fu] = father[fv];
	
}
int main(){ 
	int n,m,a,b,c;
	cin>>n>>m;
	init(n);
	for(int i=0;i<m;i++){ 
		cin>>a>>b>>c;
		if(a==1) Union(b,c);
		else{ 
			if(find_father(b)==find_father(c)) cout<<"Y"<<endl;
			else cout<<"N"<<endl;
		}
	}
	return 0;
}

注意：找父亲一定要用find_father函数,不能用father数组,为什么呢,那就留给读者自己想想(如果你能想通,说明你已经掌握了)！！完了，撒花，撒花！！