并查集（union & find）

并查集是一种树形结构，用于处理一些不交集的（Disjoint Sets）的合并及查询问题。
Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一个子集。
Union：将两个子集合并成同一个子集。

可以用于查看元素是否在一个集合里，合并两个不同的集合等等

在生活中的例子

  • 小弟 -> 老大（类似古惑仔，小弟属于洪兴的还是东星的）
  • 帮派识别
  • 两种优化方式

使用数组进行实现，?是Java代码


初始化，大家的老大都是自己

一段时间后形成这种局面，找老大就是不断的往上面寻找，一直到指向自己

集合的合并


优化一：
合并的时候约定俗称的规矩是将rank（类似树的深度）较低的子集merge到rank较高的子集中


优化二：
路径压缩，只需进行一次向上查询就好，用了优化二就不用优化一了