并查集（路径压缩）
并查集：
1.将两个集合合并
2.查询两个元素是否在一个集合当中
基本原理：每个集合用一棵树来表示，树根的编号就是整个集合的编号，每个节点存储他的父节点，p[x]表示x的父节点
问题1：如何判断树根？if(p[x] == x)
问题2：如何求x的集合编号？while(p[x] != x) x = p[x]
问题3：如何合并两个集合编号，py是y的集合编号，p[x] = y
优化：路径压缩
例题：
#include <iostream>
using namespace std;
const int N = 100010;
int p[N];//多个集合
//返回祖宗节点的值——路径压缩
int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i) p[i] = i;
while(m--)
{
char op[2];
int a, b;
scanf("%s%d%d", op, &a, &b);
if(*op == 'M') p[find(a)] = find(b);//集合合并操作
else
{
if(find(a) == find(b)) puts("Yes");
else puts("No");
}
}
return 0;
}
并查集：
在刚开始的时候，每个集合都是一个独立的集合，都只有一个数，并且集合都是等于自己本身下标的数；
例如：p[1] = 1; p[50] = 50;
如果是M操作（合并）的话，就是将 p[3] = p[5];此时集合3就被纳入到集合5里面了，称为了集合5的子集；
所以3的祖宗节点就变成了5，此时以5为祖宗节点的集合为{5,3}
如果要将集合6插入到集合3当中，就要找到集合3的祖宗节点
所以 p[6] = p[3]，也就可以 p[find(6)] = find(3)
因为6的祖宗节点本来就是6，此时以5为祖宗节点的集合就为{5,3，6}
路径压缩：
