1.并查集基本功能

并查集主要的两大功能：

1）将两个集合合并。

2）询问两个集合是否为同一个集合。

大多数算法都可以先用暴力的做法先模拟一遍，然后在其中现在简便规律，并查集可以在近乎o(1)的时间完成这两个操作。

2.并查集基本原理

每个集合用一棵树来表示，树根的编号就是整个集合的编号，每个节点存储它的父节点，p[x]表示为x的父节点。如图所示：

3.使用并查集的三个问题

1）问题1：如何判断树根：if(p[x]==x) 。需要知道除了根节点以外其他p[x]!=x;

2）问题2：如何求集合x的编号：while(p[x]!=x) x=p[x]; 如果p[x]!=x那么就让x等于它的父节点，直到找到它的根节点。

3）问题3：如何将两个集合合并：px是x集合的编号，py是y集合的编号，p[x]=y; 想要合并两个集合可以让其中一个集合的根节点的父节点等于另外一个集合的根节点。即将x集合的根结点直接接到y集合的根结点上，也就是x集合的根结点变成y了，即p[x]=y（也可以py接到px上，即p[y]=x）

4.并查集的优化（路径压缩）

     到这里你会发现并查集的运行时间还是比较大的，尤其是在求集合x的编号时。这里一点就是在查找一个结点的祖宗结点（查找集合编号）时有一个路径压缩，就是当查找x结点的祖宗结点时，让这一条路径上的所有经过结点都指向祖宗结点。  

 路径压缩使得在查找集合x的编号时只需要搜一遍，使得整个过程在近乎o(1)的时间完成。

5.并查集模板

利用递归，实现寻找祖宗结点+路径压缩，整个代码的重点就在find函数上了

#include<iostream>
using namespace std;
const int N=100010;
int f[N];//父节点
int find(int x)//返回x的祖宗节点+路径压缩
{
   if(f[x]!=x)  f[x]=find(f[x]);//如果它不等于它的父节点，那么就让它的父节点等于它的祖宗节点
   return f[x];//返回它的父节点
}

6.例题

例题：AcWing 836 合并集合

题目描述
一共有n个数，编号是1~n，最开始每个数各自在一个集合中。现在要进行m个操作，操作共有两种：“M a b”，将编号为a和b的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；“Q a b”，询问编号为a和b的两个数是否在同一个集合中；
输入格式
第一行输入整数n和m。接下来m行，每行包含一个操作指令，指令为“M a b”或“Q a b”中的一种输出格式
对于每个询问指令”Q a b”，都要输出一个结果，如果a和b在同一集合内，则输出“Yes”，否则输出“No”。每个结果占一行。

数据范围
1≤n,m≤100000

#include<iostream>//c++
using namespace std;
const int N=100010;
int f[N];//父节点
int find(int x)//返回x的祖宗节点+路径压缩
{
   if(f[x]!=x)  f[x]=find(f[x]);//如果它不等于它的父节点，那么就让它的父节点等于它的祖宗节点
   return f[x];//返回它的父节点
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);//输入n和m
    for(int i=0;i<n;i++)
    {
        f[i]=i;//初始化每个节点都为一个独立的集合
    }
    while(m--)
    {
        char op[2];
        int a,b;
        scanf("%s%d%d",op,&a,&b);
        if(op[0]=='M')//合并
        {
            if(find(a)!=find(b))
                 f[find(a)]=find(b);//将x集合的根结点直接接到y集合的根结点上，也就是x集合的根结点变成y了，即f[find(a)]=find(b)
        }
        else//查询
        {
            if(find(a)==find(b))   printf("Yes\n");
            else  printf("No\n");
        }
    }
}