并查集很巧妙的使用数组模拟了森林合并树的结构
初始化节点时同时记录每个节点的父节点(初始指向自己)
动态连通性实际上是一种等价关系
并查集中的连通满足三性质
- 自反性，节点p和自己是连通的
- 对称性，如果节点p和节点q是连通的，那么节点q和节点p也是连通的
-传递性，如果节点p和q是连通，节点q和r连通，那么节点p和r也连通
并查集中实现三个功能：
- 连接p和q union
- 判断p和q是否连通 connected
- 求图结构中的连通分量 count
实现并查集实现三个函数：find、union、connected
高度小的树接到大的树下面可以尽量保持树的平衡性(通过记录每个节点下面的节点个数实现)，使得时间复杂度从O(N)降低到O(log(N)).
通过父子节点的迭代实现路径压缩
while (parent[x] != x)
// 进行路径压缩
parent[x] = parent[parent[x]]
x = parent[x]
}
调用find函数每次向树根遍历的同时，顺手将树高缩短了，最终所有树高都不会超过 3
很多实用dfs解决的问题都可以实用DFS解决.
