DSU¶

Find¶

The find operation is used to determine the representative of an element. It is employed when you need to identify the representative of the set containing the element \(x\).

• The first method, used for lists, works by simply returning the value of the array \(Rep[x]\).

int Find(int x) {
    if (Rep[x] == x)
        return x;
    return Find(Rep[x]);
}

int Find(int x){
    return Rep[x];
}

1int find(int x) {
2    while (par[x] != x) {  // This line moves from x to the root
3        x = par[x];
4    }
5    return x;
6}

int Find(int x){
    if (Par[x] == x)
        return x;
    return Find(Par[x]);
}

Union¶

Merges two sets and forms a new set. Suppose we merge two sets containing two members \(x\) and \(y\).

• First, we find the representatives of these two members. Let's assume they are \(X\) and \(Y\), respectively. If \(X\) and \(Y\) are the same, it means the two members are in the same set, and we do not need to perform a merge. If they are not equal, we set the representative of the members of one set to be the representative of the members of the other set. The key point is that we change the representative of the set with fewer members. This is because the order of this operation is \(O(n \lg(n))\) (the representative of each member changes at most \(\lg(n)\) times, since in each step, the number of members in the group whose representative changes doubles). This technique of merging the smaller set into the larger one is called Union by Rank.

void Union(int x, int y){
    x = Find(x);
    y = Find(y);
    if (x == y)
        return;
    if (sz[x] < sz[y])
        swap(x, y);
    sz[x] += sz[y];
    for (int z : lst[y]){
        Rep[z] = x;
        lst[x].push_back(z);
    }
    lst[y].clear();
}

Another method available for merging is when we consider the sets as a forest. In this case, similar to the previous section, we can compare the number of vertices in each component (set) and assign the representative of the component with fewer vertices to the representative of the other component. In this way, to find the root of the component of an arbitrary vertex, the Find function is called at most \(lg(n)\) times (in other words, the height of each tree in the forest is at most \(lg(n)\)).

void Union(int x, int y){
    x = Find(x);
    y = Find(y);
    if (x == y)
        return;
    if (sz[x] < sz[y])
        swap(x, y);
    sz[x] += sz[y];
    Par[y] = x;
}

Path Compression¶

Now, if we use the Path Compression technique in the Find function to find the root, we can improve our amortized complexity. In this method, while searching for the root of \(x\), at the end we set the parent of \(x\) to be the root. This technique, called Path Compression, causes all vertices along the path from \(x\) to the root to update their parent to the root. As a result, the number of children of the root increases. This shortens the path from \(x\) to the root (refer to the Find function for a better understanding) and reduces the amortized complexity of each operation to \(O(lg^*n)\). This means for \(n = 10^6\), only five operations are needed (\(lg^*n\) represents the number of times we need to take the logarithm of \(n\) until we reach 1. For example, \(lg^*4 = 2\) because taking the logarithm of 4 once gives 2, and taking it again gives 1, resulting in two total operations). In general, \(lg^*n\) is at most 5 for \(n\) smaller than \(2^{65536}\), demonstrating the efficiency of Path Compression.

An important note is that even if Path Compression is used without Union by Rank, the amortized complexity of each operation will be \(O(lg(lg(n)))\), which in practice is nearly indistinguishable from using Union by Rank!

int Find(int x){
    if(Par[x] != x)
        Par[x] = Find(Par[x]);
    return Par[x];
}

Undo¶

Undoes the last merge operation and separates the two merged sets. Assume we do not use Path Compression. In this case, each call to the merge function only changes the values of \(sz_x\) and \(Par[y]\). Therefore, we can save the changes we make so that when an undo is needed, we can revert to the previous values of these two variables. This allows us to implement each undo operation in \(O(1)\).

Note that having an undo function makes it impossible to use Path Compression, as our time complexity will no longer remain efficient (recall that Path Compression's complexity is amortized efficiently, and a single call to the Find function alone could even take \(O(n)\) time).

int Find(int x){
    if(Par[x] == x)
        return x;
    return Find(Par[x]);
}

void Union(int x, int y){
    x = Find(x);
    y = Find(y);
    if (x == y)
        return;
    if (sz[x] < sz[y])
        swap(x, y);
    operations.push_back(make_pair(y, sz[y]));
    sz[x] += sz[y];
    Par[y] = x;
}

void Undo(){
    int y = operations.back().first;
    sz[y] = operations.back().second;
    operations.pop_back();
    int x = Find(y);
    sz[x] -= sz[y];
    Par[y] = y;
}