union_find_rank.cc

/*
An improvement of the Disjoint-Set Forest is to control tree heights storing in each node
its rank, which is an upper bound for its height. When a node is initialized, its rank is
set to zero. To merge trees with roots x and y, first compare their ranks. If the ranks
are different, then the larger rank tree becomes the parent, and the ranks of x and y do
not change. If the ranks are the same, then either one can become the parent, but the new
parent's rank is incremented by one. While the rank of a node is clearly related to its
height, storing ranks is more efficient than storing heights. The height of a node can
change during a Find operation, so storing ranks avoids the extra effort of keeping the
height correct. This method ensures that trees do not become too deep.

This allows to further reduce the time complexity of Find and Union operations from
O(log n) to O(alpha(n)), where alpha is the inverse Ackermann function, which grows much
slower than O(log n). More precisely, alpha(n) < 5 for any practical n:

https://en.wikipedia.org/wiki/Ackermann_function#Inverse

Instead of using rank, an alternative implementation is to use the size of the components.

NB: By definition, Disjoint-Set Forests cannot be used to represent cyclic graphs, for
which we can use BFS or DFS.

Notable problems solved by Union-Find:
1. Least Common Ancestor of a pair of nodes in a tree.
2. Depth determination in a tree or forest.
3. The Offline Minimum Problem (Insert and Extract-min operations). This is a way of
   implementing a priority queue.
*/

class UnionFindRank {
    unordered_map<int, int> id, rank;
    int islands; // connected components
public:
    int find(int a) {
       //return id[a] == a ? a : (id[a] = find(id[a])); // if we don't need to count the islands
       if (!id.count(a)) id[a] = a, islands++;
       if (a != id[a]) id[a] = find(id[a]);
       return id[a];
    }

    void connect(int a, int b) {
       a = find(a), b = find(b);
       
       if (a == b) return;
       
       if (rank[a] < rank[b]) swap(a, b);
       
       id[b] = a;
       if (rank[a] == rank[b]) rank[a]++;

       --islands;
    }

    /* // Union by size
    void connect(int a, int b) {
       a = find(a), b = find(b);

       if (a == b) return;
        
       if (size[a] < size[b]) swap(a, b);
        
       id[b] = a;
       size[a] += size[b];
       
       --islands;
    }
    */

    bool connected(int a, int b) { return find(a) == find(b); }

    int getCount() { return islands; }
};