并查集

描述：

​ 可以快速地做到下列两个操作：（1）将两个集合合并（2）询问两个元素是否在一个集合

代码模板：

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

代码解释：

find函数的实现

（1）int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]); //只要没有找到祖宗节点，就一直找，因为只有祖宗节点的 p[x] = x;
return p[x]=x; //找到了祖宗节点，便返回祖宗节点的值
}
这个函数既实现了找到祖宗节点的功能，又实现了将所有儿子节点直接指向祖宗节点，即路径压缩
（2）合并两个集合，即将其中一个集合的祖宗节点变成另一个祖宗节点的子节点
p[find(a)] = find(b);
（3）判断两个集合是否在同一个集合：则判断其祖宗节点是否为是否为同一个节点即可
if(find(a) == find(b))printf(“Yes\n”);
else printf(“No\n”);