并查集

并查集

并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素

并查集支持：

• 查找：查询元素所属集合
• 合并：合并两个集合

初始化

初始时，每个元素为一个集合，一个指针指向自身表示该集合由该元素代表

查询

通过给定的节点，不断沿着指针查询集合代表直到根节点

• 路径压缩：当一个集合节点越来越多时，每次查询都可能要经过很长的链路，为此我们可以在每次查询时，将查询路径上所有节点的指针指向根节点，这样就压缩了查询的路径

  

合并

要合并两个集合，只需将一个集合的根节点指向另一个集合的根节点即可

在合并时，我们希望树高较小的集合合并到树高较大的集合，尽可能地减少树高，防止后续查询链路过长