西窗月

Disjoint-set (union find)

Union

Assume we initialize each node’s parent is itself. root[i] = i

Union operation is just to set one root to be a child of another root.

void union_root(int x, int y) {
    int r1 = find_root(x);
    int r2 = find_root(y);
    if (r1 != r2) {
        root[r1] = r2;
    }
}

Find

The plain version is to find root of its parent until its parent is itself.

int find_root(int x) {
    if (x!=root[x]) {
        return find_root(root[x]);
    }
    return root[x];
}

Path compression (No reason not to use.)

int find_root(int x) {
    if (x!=root[x]) {
        root[x] = find_root(root[x]);
    }
    return root[x];
}

or

int find_root(int x) {
    while (x!=root[x]) {
        root[x] = root[root[x]];
        x = root[x];
    }
    return root[x];
}

Reference

princeton slide