并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。常常在使用中以森林来表示。
一，对并查集的认识
并查集是树形结构，常常在题目中用来判断两个元素是否属于同一个集合，每个集合都有一个特征性元素称为这个集合的father，如果两个元素的father相同，则说明这两个元素属于同一集合,若这两个元素的father不相同，则说明这两个元素不属于一个集合。并查集就是这样一种支持合并和查询的树形数据结构。在题目中的应用有，判断两个点是否属于同一个联通块，最小生成树kruskal算法中，判断加边是否会有环等。
在考察并查集的题目中，一般我们用一个f数组来实现并查集的功能，起初所有的f[i]=i;证明所有元素都是单独一个集合。
//并查集初始化
for(int i=1;i<=n;i++) f[i]=i;
二，并查集的基本操作
1，并查集的合并操作（merge）
简而言之，就是将两个元素所在的集合合并成一个集合，操作简单，首先我们只需要找到两个集合的特征性元素，然后把其中一个特征性元素变成另一个，这样两个集合特征性元素相同，两个集合就合并在了一起，在merge操作中我们运用到了按秩合并来优化。
inline void merge(int f1,int f2)
{
f[f1]=f2;
return; }//普通合并
按秩合并：所谓秩就是树高，按秩合并就是按照秩序合并，起初我们给每个点赋高为一，以后在每次合并的过程中，都用树高小的指向树高大的，这样可以保证树高不超过log2N,把查询的最坏复杂度从O(n)减小到O(logn)。
inline void merge(int x,int y)
{
int f1=find(x);
int f2=find(y);
if(f1!=f2)
{
if(rank[x]<=rank[y]) f[f1]=f2,rank[y]=max(rank[y],rank[x]+1);
else f[f2]=f1,rank[x]=max(rank[x],rank[y]);
}
return;}
2,并查集的查询操作
就是查询两个元素是否属于同一个集合，首先我们要先找到这两个元素所在集合的特征性元素。如果两个特征性元素相同，则两个元素属于同一个集合，否则属于两个集合，其中我们用到路径压缩来优化，路径压缩就是在查询过程中，从此节点到根节点路径上的所有节点的f全部改为根节点，这样在下次查询时，就可以减少递归过程从而达到优化的目的。
inline int find(int k)
{
if(f[k]==k) return f[k];
return f[k]=find(f[k]);
}
*:按秩合并和路径压缩不可以同时使用，一般我们使用路径压缩来优化。
并查集完整代码（洛谷P3367）
#include<cstdio>
#include<iostream>
using namespace std;
int n,m,f[10005];
int find(int k)
{
if(f[k]==k) return f[k];
return f[k]=find(f[k]);
}
void merge(int x,int y)
{
int f1=find(x);
int f2=find(y);
if(f1!=f2) f[f1]=f2;
return;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) f[i]=i;
for(int i=1;i<=m;i++)
{
int xi,yi,zi;
scanf("%d%d%d",&zi,&xi,&yi);
if(zi==1) merge(xi,yi);
else if(zi==2)
{
int f1=find(xi);
int f2=find(yi);
if(f1==f2) printf("Y
");
else printf("N
");
}
}
return 0;
}
祝各位OIER NOIP2019 RP++ SCORE++