“This is the 11th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

Do not know whether we know and look up this algorithm, I have never heard before (ignorant), in fact, this algorithm is a very common algorithm, but also can use fixed routines to solve a certain kind of problems, the most classic is the relative problem.

UnionFind is often used to handle merge and query problems with disjoint sets.

UnionFind has two functions: Union and Find

  • Union: To combine two disjoint sets into a single set.
  • Find: Queries two elements to see if they are in the same set (to determine if they are related, using Find to get their ancestry).

Two trees:

After Union 1,5

Classic case: relatives

If someone’s family is too large, how do you know if two of them are related?

X is related to y, y is related to Z, so x is related to z. If X and y are relatives, then a relative of X is a relative of Y, and a relative of Y is a relative of X.

At this time, we can use and look up set algorithm to associate each relative with Union. After all relatives are recorded, we can use and look up Find in the set. We can obtain their ancestors through Find to see if they are the same ancestors, so as to determine whether they are relatives.

Time complexity: ELogn (assuming a set of E)

And search set steps:

  • Initialization: Initialize the set of each point as itself (time complexity O(n))

  • Find: Find the set of two elements, find the root node (time complexity O(logn))

    • Recursive search
    • Find the root node and recursively return with all nodes in the recursive path marked as root nodes (this is more efficient, and even less efficient if each node stores only the upper-level nodes)

  • Merge: Combine two elements into one set if they belong to different sets (time complexity O(1))

    • Find the root node of both elements
    • If not, change the ancestor of one element to the ancestor of another.

The meaning of the array in UnionFind: the subscript represents the node of the tree and the value represents the root node of the node (initialization assumes itself to be its own root node)

When we use union(1,2), the array becomes

The two trees in the figure above are represented in arrays

Using union(1,5), the array looks like this:

This causes us to call find(9) to happen

Find (9) -> find(5) -> find(1) = 1

In the scenarios that need to use and look up the set, the frames used are almost the same each time, and we only need to adjust the template to meet most of the requirements. Below is an algorithm template for look up the set. Through simple optimization of union, the number of ancestor Settings can be reduced, so as to achieve quickUnion.

And look up the set template code:

package com.zhj.leetcode; public class UnionFind { public int[] fa; public int[] rank; public UnionFind(int length){ init(length); } public init(int length){fa = new int[length]; rank = new int[length]; for (int i = 0; i < length; i++) { fa[i] = i; rank[i] = 0; @param x * @return */ public int find(int x) {if (x == fa[x]) {return x; } return fa[x] = find(fa[x]); } @param x * @param y */ public void union(int x, int y) {int faX = find(x); int faY = find(y); if (faX ! = faY) { fa[faX] = faY; Public void quickUnion(int x, int y) {int faX = find(x); public void quickUnion(int x, int y) {int faX = find(x); int faY = find(y); if (faX ! = faY) { if (rank[faX] > rank[faY]) { fa[faY] = faX; } else if (rank[faX] < rank[faY]){ fa[faX] = faY; } else { fa[faY] = faX; rank[faX] += 1; }}}}Copy the code