通过 6 人介绍可以认识世界上任何一个人？( 二 ) _朋友圈

更新合并
将权重小的集合的根指向权重大的集合的根(此操作是为尽量降低树的深度) 。

文章插图
查找
判断 2 个元素是否属同一集合，只需向上查找根，再判断是否相同。
过程中做路径压缩，加快下一次查找速度。

文章插图
代码实现
查找

int findFather(int s) {int root = s, temp;// 查找s的最顶层根while (father[root] >= 0) {root = father[root];}// 路径压缩 ， 提高后续查找效率while (s != root) {temp = father[s];father[s] = root;s = temp;}return root;}

合并

void unionSet(int s, int e) {int rootS = findFather(s);int rootE = findFather(e);int weight = father[rootS] + father[rootE];// 将结点数少的集合作为结点数多的集合的儿子节点if (father[rootS] > father[rootE]) {father[rootS] = rootE;father[rootE] = weight;} else {father[rootE] = rootS;father[rootS] = weight;}}

程序员如何避免陷入“内卷”、选择什么技术最有前景，中国开发者现状与技术趋势究竟是什么样？快来参与「2020中国开发者大调查」，更有丰富奖品送不停！
戳：