Union-Find Algorithm
This article will resolve
LeetCode | Difficulty |
---|---|
130. Surrounded Regions | 🟠 |
323. Number of Connected Components in an Undirected Graph🔒 | 🟠 |
684. Redundant Connection | 🟠 |
990. Satisfiability of Equality Equations | 🟠 |
Prerequisites
Before reading this article, you need to learn:
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 term "connected" here refers to an equivalence relation, which means it has the following three properties:
Reflexivity: Node
p
is connected to itself.Symmetry: If node
p
is connected to nodeq
, thenq
is connected top
.Transitivity: If node
p
is connected toq
, andq
is connected tor
, thenp
is connected tor
.
For example, in the previous graph, any two different points from 0 to 9 are not connected, and calling connected
will return false, resulting in 10 connected components.
If we now call union(0, 1)
, then 0 and 1 become connected, reducing the connected components to 9.
Calling union(1, 2)
next will make 0, 1, and 2 connected, and calling connected(0, 2)
will return true, reducing the connected components to 8.

Determining such an "equivalence relation" is very practical, such as compilers determining different references of the same variable, or calculating friend circles in social networks, etc.
Now, you should have a rough understanding of what dynamic connectivity is. The key to the Union-Find algorithm lies in the efficiency of the union
and connected
functions. So, what model represents the connectivity of this graph? What data structure should be used to implement the code?