隐藏与 Union-find 不相关的细节;可以使用整数快速获取与对象相关的信息(数组的下标);可以使用符号表对对象进行转化。
简化有助于我们理解连通性的本质。...如图 1 所示,假设我们有编号为 [0,1,2,3,4,5,6,7,8,9] 的 10 个对象,对象的不相交集合为 : {{0},{1},{2,3,9},{5,6},{7},{4,8}} 。...比如 Union(3,6) ,需要将 id 为 id[3] = 9 的所有对象 {2,3,4,9} 的 id 均修改为 id[6] = 6 ,如下图所示。
?...如图所示,id[2] = 9 就表示 2 的父结点为 9;3 的根节点为 9 (3 的父结点为 4,4 的父结点为 9,9的父结点还是 9,也就是根结点了),5 的根结点为 6 。...你可能需要回溯一棵瘦长的树(斜树),每个对象只是指向下一个节点,那么对叶子节点执行一次查找操作,需要回溯整棵树,只进行查找操作就需要花费 N 次数组访问,如果操作次数很多的话这就太慢了。