并查集

并查集的两个操作：

1. 将两个集合合并；
2. 询问两个元素是否在同一个集合中；

基本原理：

每个集合用一棵树表示，树根的编号就是整个集合的编号，每个节点只需储存它的父节点的值，当p[x] == x时，表示为树的根节点。

两个关键问题：

1. 如何判断根节点：if(p[x] == x)
2. 如何求x的集合编号：while(p[x] != x) x = p[x]
3. 如何合并两个集合：设x, y分别为两个集合（两个树）的根节点p[x] = y(或p[y] = x)

优化：路径压缩

当查找某个集合中一个点x的根节点时，顺便将其查找路径上的点（即这个点x与根节点之间的所有点）的状态一并更新，那么此后的点更新状态时，只需找到点x即可，达到近乎O(1)的时间复杂度

AcWing 836. 合并集合