并查集

并查集的理解

作为一种数据结构，其核心的是修改与查询，并查集实现的是1.将两组的内容合并以及2.查询两个元素是否在同一组内。

并查集的结构往往是以树的形式呈现，所谓的同一组就是是否在同一棵树下，将两组的内容合并就是将一颗的根节点嫁接到另一根树的根节点下面，查询两个元素是否在同一组内就是看两个结点是否在同一棵树下。

并查集的核心函数

合并两棵树

void merge(int x,int y){
    fa[x]=y;
}

查询结点对应的树的根节点(这里进行了路径压缩的优化，对于每次的搜索结果，将该结果记录到相关结点上)

int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);//fa数组表示该结点对应的树的根节点，但是由于合并结点时只是两棵树的根节点的合并，并没有将相关信息下穿到两棵树的其他孙子结点，所以需要向上查询
}

数组初始化为每个结点自身，即

如果还需要记录相关组内的相关信息，也可以将相关值记录在该组的根节点上，再合并过程中需要进行合并更新。