# Union-Find 并查集算法

Info

**已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~**

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

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 "connectivity" mentioned here is 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 node`q`

, then`q`

is also connected to`p`

.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?