并查集

一、适用的问题

1.将两个集合合并

2.询问两个元素是否在同一个集合当中

二、基本原理

每个集合用一棵树表示，树根的编号就是每个集合的编号。每个节点都存储它的父节点，p[x]里面存的值是x的父节点。

三、问题

1.如何判断树根：if(p[x] == x)

2.如何求x的集合编号：while(p[x] != x) x = p[x];

3.如何合并两个集合：p[x]是x的集合编号，p[y]是y的集合编号。p[x] = y

四、优化

路径压缩：求x的集合编号时，如果找到过一次根节点，那么就把所有子节点都指向根节点。

五、核心操作（返回根节点 + 路径压缩）

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