Check and set

1 Concept Introduction

In computer science, parallel Sets are a tree structure, which is used to deal with the problem of merging and querying Disjoint Sets [1]. There are two main operations to query the set, which are:

  • Find: Find
  • The Union:

Where Find is to determine which category a given element belongs to. Often an element in a set of categories is used as the Root element to represent this category, so the Find operation is actually the corresponding Root value of this element. If two elements have the same Root value, they are of the same category.When you build and look up sets, you encounter the merging of two categories into a single category, known as a Union. As described above for the Find operation, change the Root value for all elements in the original two categories to the same value.

2 Code Templates

2.1 Naive and set lookup

The Find and Union operations are implemented and looked up by definition, regardless of efficiency. The core point is a p array that maintains the element’s parent element value or Root value (Path to the compression), when an element’s p value is itself, then the node is Root.Where, p value is the Root corresponding to the element and query set efficiencyhigher, the following template shows the algorithm implementation in this case.

void MakeSet(int size)
{
    // Initialize and look up the set, setting each element's P value to its own
    // Suppose the value of the node is 1~size(including size)
    for (int i = 1; i <= size; i++) { p[i] = i; }}int Find(int n)
{
    // Determine the type of element n, that is, find the Root element value of element N
    if(p[n] ! = n) { p[n] =Find(p[n]); // Non-root nodes, continue to look up, and assign values
    }
    return p[n];
}

void Union(int n, int m)
{
    // Merge the categories of elements n and m
    // Simply point the Root of one element in n and m to the Root of the other element
    int rootA = Find(n);
    int rootB = Find(m);
    p[rootA] = rootB;  // Root of n points to Root of m
}
Copy the code

2.2 Maintain and query the Size of the element set

In contrast to the plain set lookup algorithm implementation, a size array is maintained to hold the current number of elements in each category. By default, only the size array value of the Root node is valid.

void MakeSet(int size)
{
    // Initialize and look up the set, setting each element's P value to its own
    // Suppose the value of the node is 1~size(including size)
    for (int i = 1; i <= size; i++) {
        p[i] = i;
        / /! Add the size array
        size[i] = 1; }}int Find(int n)
{
    // Determine the type of element n, that is, find the Root element value of element N
    / /! The Find operation does not need to update the size array
    if(p[n] ! = n) { p[n] =Find(p[n]); // Non-root nodes, continue to look up, and assign values
    }
    return p[n];
}

void Union(int n, int m)
{
    // Merge the categories of elements n and m
    // Simply point the Root of one element in n and m to the Root of the other element
    int rootA = Find(n);
    int rootB = Find(m);
    p[rootA] = rootB;  // Root of n points to Root of m
    / /! RootB is the new Root. You only need to update the size value of rootB
    size[rootB] += size[rootA];

}
Copy the code

Related LeetCode example

LeetCode and check the set topic

[1] and look up the set – Wikipedia