**Translator: [Ziming](https://github.com/ML-ZimingMeng/LeetCode-Python3)**

**Author: [labuladong](https://github.com/labuladong)**

Many readers in the previous article expressed interest in the Union-Find algorithm, so in this article, I will take a few LeetCode problems to talk about the ingenious use of this algorithm.

First, let's recall that the Union-Find algorithm solves the problem of dynamic connectivity of the graph, but the algorithm itself is not difficult. Your ability which is to abstract the original problem into a question about graph theory to abstract the problem determines whether you can solve it.

In my opinion, when it comes to time complexity, indeed, it is also O (1) without the need for weight balance. However, if the size array is added, the efficiency is still slightly higher, such as the following:

If weight balance optimization is carried out, case 1 will surely be obtained, without weight optimization, case 2 may occur. The `while` loop of path compression is triggered only when the height is 3, so case 1 will not trigger path compression at all, while case 2 will perform path compression many times to compress the nodes in the third layer to the second layer.

void solve(char[][] board);

PS: This reminds me of the chess game "Othello" when I was a kid. As long as you use two pieces to sandwich each other's pieces, the opponent's pieces will be replaced with yours. Similarly, the pieces occupying the four corners are invincible, and the side pieces connected to it are also invincible (cannot be clipped).

**Those `O` which do not need to be replaced have a common ancestor called` dummy`. These `O` and` dummy` are connected to each other,however, those `O` that need to be replaced are not connected to` dummy`**.

This is the core idea of Union-Find and it is easy to understand the code if you understand this diagram.

}

To be honest, the Union-Find algorithm solves this simple problem. It can be a bit of a killer. It can solve more complex and more technical problems. **The main idea is to add virtual nodes in a timely manner. Dynamic connectivity**.

Return true if and only if it is possible to assign integers to variable names so as to satisfy all the given equations.

```java

boolean equationsPossible(String[] equations) {

**Translator: [Ziming](https://github.com/ML-ZimingMeng/LeetCode-Python3)**

**Author: [labuladong](https://github.com/labuladong)**

Today I will talk about the Union-Find algorithm, which is often referred to as the Disjoint-Set algorithm, mainly to solve the problem of "dynamic connectivity" in graph theory. Nouns look a little confusing, but they ’re really easy to understand. We will explain it later. Moreover, the application of this algorithm is also very interesting.

Speaking of this Union-Find, it should be my "Enlightenment Algorithm", this algorithm was introduced at the beginning of *Algorithms 4th edition*, I have to say that this algorithm shocked me! Later I discovered that leetcode also has related topics and is very interesting. Moreover, the solution given in *Algorithms 4th edition* can be further optimized. With only a small modification, the time complexity can be reduced to O (1).