I try to learn `Union Find`

algorithm.
There is a function that accepts vertex number of graph:

// 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; }

Full code is provided by link

I can’t get what is happening here:

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

Income vertex `p`

is assinged to `root`

. Then something happens in loop.

## Answer

`this.id`

is a mapping between indices from current to parent. The loop tries to follow the mapping starting at `p`

, one mapping step at a time and stops if it finds a mapping that maps to itself.

For `[0,2,0]`

starting at `p=1`

we see a 2, go to index 2, see a 0, go to index 0, see a 0 again, are done.