Intento aprender el algoritmo Union Find . Hay una función que acepta el número de vértice del gráfico:
// Find which component/set 'p' belongs to, takes amortized constant time. find(p) { // Find the root of the component/set let root = p; while (root != this.id[root]) root = this.id[root]; // Compress the path leading back to the root. // Doing this operation is called "path compression" // and is what gives us amortized time complexity. while (p != root) { let next = this.id[p]; this.id[p] = root; p = next; } return root; }El código completo se proporciona por enlace
No puedo entender lo que está sucediendo aquí:
let root = p; while (root != this.id[root]) root = this.id[root]; El vértice de ingresos p se asigna a root . Entonces algo sucede en bucle.
this.id es un mapeo entre índices de actual a principal. El ciclo intenta seguir el mapeo comenzando en p , un paso de mapeo a la vez y se detiene si encuentra un mapeo que se mapea a sí mismo.
Para [0,2,0] a partir de p=1 , vemos un 2, vamos al índice 2, vemos un 0, vamos al índice 0, vemos un 0 de nuevo, hemos terminado.