What does loop do with graph vertexes in Union Find algorithm?-CodePudding

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.

CodePudding user response：

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.