并查集(Union Find)算法中针对图顶点的循环作用是什么？

首先明确Union Find的核心存储规则：this.id是父节点指针数组，对任意顶点x，this.id[x]存储的是x的父顶点编号。如果一个顶点的父节点是它自己，说明这个顶点就是它所在连通分量的根节点，根节点是一个连通分量的唯一标识。

你提问的这段代码作用是从传入的顶点p出发，沿着父节点指针一路向上溯源，直到找到p所属连通分量的根节点：

let root = p;
while (root != this.id[root])
       root = this.id[root];

我们可以用一个具体场景理解执行流程：

• 假设现有连通分量的父子关系为：3的父是2，2的父是1，1的父是1（1是该分量的根节点）
• 当传入的p=3时，初始root=3
• 第一次判断3 != this.id[3]（等价于3≠2），条件成立，root更新为2
• 第二次判断2 != this.id[2]（等价于2≠1），条件成立，root更新为1
• 第三次判断1 != this.id[1]（等价于1≠1），条件不成立，循环终止
• 最终得到的root=1就是p=3所属连通分量的根节点

后续的路径压缩逻辑就是基于这个找到的根节点，把p到根路径上所有节点的父节点直接指向根，下次查询这些节点时就能一步到位拿到根，这也是并查集查询均摊时间复杂度接近O(1)的核心原因。

内容的提问来源于stack exchange，提问作者user14514318