Union-Find Algorithm

The Union-Find algorithm is specifically designed for "dynamic connectivity." I have written about it twice before. Due to its high frequency in exams and its role as a prerequisite for minimum spanning tree algorithms, I have consolidated this article to explain the algorithm clearly in one go.

First, let's start with what dynamic connectivity in graphs is.

I. Dynamic Connectivity

Simply put, dynamic connectivity can be abstracted as connecting lines in a graph. For example, in the following graph, there are 10 nodes that are not connected to each other, labeled from 0 to 9:

Now, our Union-Find algorithm mainly needs to implement these two APIs:

class UF {
    // connect p and q
    public void union(int p, int q);
    // determine if p and q are connected
    public boolean connected(int p, int q);
    // return the number of connected components in the graph
    public int count();
}

class UF {
public:
    // connect p and q
    void union_(int p, int q) = 0;

    // determine if p and q are connected
    bool connected(int p, int q) = 0;

    // return the number of connected components in the graph
    int count() = 0;
};

class UF:
    # connect p and q
    def union(self, p, q):
        pass
    
    # determine if p and q are connected
    def connected(self, p, q):
        pass

    # return the number of connected components in the graph
    def count(self):
        pass

type UF struct{}
// connect p and q
func (uf *UF) Union(p int, q int) {}
// determine if p and q are connected
func (uf *UF) Connected(p int, q int) bool {
   return false
}
// return the number of connected components in the graph
func (uf *UF) Count() int {
   return 0
}

var UF = function() {
    // connect p and q
    this.union = function(p, q) {}; 

    // determine if p and q are connected
    this.connected = function(p, q) {};

    // return the number of connected components in the graph
    this.count = function() {};
};

The "connectivity" mentioned here is an equivalence relation, which means it has the following three properties:

1. Reflexivity: Node p is connected to itself.

2. Symmetry: If node p is connected to node q, then q is also connected to p.

3. Transitivity: If node p is connected to node q, and q is connected to node r, then p is also connected to r.

For example, in the previous diagram, any two different points from 0 to 9 are not connected. Calling connected will return false, and there are 10 connected components.

If we now call union(0, 1), then 0 and 1 become connected, reducing the number of connected components to 9.

Calling union(1, 2) next, 0, 1, and 2 are all connected. Calling connected(0, 2) will also return true, reducing the connected components to 8.

Judging this "equivalence relation" is very practical, such as a compiler determining different references to the same variable, or calculating friend circles in a social network.

Now, you should have a basic understanding of dynamic connectivity. The key to the Union-Find algorithm lies in the efficiency of the union and connected functions. So, what model should we use to represent the connectivity state of this graph? And what data structure should we use to implement the code?