define

The search set is a tree data structure, which, as its name implies, is used to deal with some non-intersection merge and query problems. It supports two operations:

  • Find: To determine what subset an element is in;
  • Merge (Union) : Combine two subsets into one set.

background

A popular story is told: several families have a banquet, but the longevity of the family is universal, so there are many people. Due to long periods of separation and aging, these people gradually forget their relatives and only remember who their father was, while the father of the oldest (called “ancestor”) has died and he only knows himself as the ancestor. To find out which family they belonged to, they came up with a way to simply ask their father if he was the ancestor, and they went up and down until they got the ancestor. To determine whether two people are from the same family, they can simply look at whether their ancestors are the same person.

structure

And look up the term tree structure itself, usually represented by an array, where each node records who its parent is

Each time the root is compared, the current set is added if the condition is met

Use trilogy

Initialize the

Initialization creates an array of the same number of elements that represent the parent of element I and is presented as itself, and the parent of each element in its initial state is itself

int fa[MAXN];
void init(int n){
    for (int i = 1; i <= n; ++i)
        fa[i] = i;
}
Copy the code

The query

Using recursion, the parent node is accessed layer by layer until the root node is found. If you need to determine whether two elements are in the same set, you only need to look at whether the root node is the same

int find(int x){
    if(fa[x] == x)
        return x;
    else
        return find(fa[x]);
}
Copy the code

merge

To add an element or a group of elements to the current tree, you only need to set the parent node of the element to be added to the current node

Note that this is the merge of two elements, not the elements themselves

void merge(int i, int j){ fa[find(i)] = find(j); } void merge(int I, int j){find(I) = j; }Copy the code

Path to the compression

If you keep adding elements to it, the tree structure becomes very long and finding nodes becomes time-consuming, so you can use path compression to flatten the tree structure

int find(int x){ if(x == fa[x]) return x; else{ fa[x] = find(fa[x]); Return fa[x]; // Return parent node}}Copy the code

Related topics

Redundant links

To found the tree

Account merge