This evening, senior students are going to explain and check the collection. In fact, I have heard of this algorithm for a long time from my previous blog, and the reason for many competitions is that I will not be rebuffed repeatedly. So take advantage of the day today free, first preview and check the collection. Here’s a quick summary.

First check out the portal blog

Here, I first give two definitions of my own (Would be wrong) –The parent nodeandThe root node
whenC->B->A(->Indicate affiliation)
1.A is the parent node and root node of B.
2.A is the root of C.
3.B is the parent of C.

First, and the lookup set consists of two arrays (pre[],tong[]) and two functions (find(),mix()).

pre[i]Represents the root of I.

tong[i]Marks all parentsi.

Let’s do an example from the last one:HDUOJ

They give you a number of towns, and then they give you a number of roads from town A to town B, and you have to figure out how many more roads you need to build to connect all of them. This is a classic parallel set problem. With the sample

Example Input:7 5

4 2
2 3
3 5
2 1
6 7
Copy the code

So for example we can think of 4 as the parent of 2, 2 as the parent of 3, 3 as the parent of 5, 2 as the parent of 1, and 6 as the parent of 7. You get something like this

Figure 1

Then look at how many root nodes there are in the end. Since only all root nodes need to be connected to connect all towns (as shown in figure 6 and 4), the total number of roads to be built in the end is the number of root nodes -1.

Let’s start with two and look up the set template functions
int find(int x) // find the root
{
    int r = x; // find the root of x, r
    while(pre[r] ! = r) r = pre[r];int temp, i;
    i = x;
    //* Compression path
    // Convert all nodes below root r to children of r.
    while(pre[i] ! = r) { temp = pre[i];//temp records the parent of I before changing it to the root of I.
        pre[i] = r;    // Change the parent of I to the root of I
        i = temp;      / / loop
    }
    return r; // The primary goal of find is to return the root of x
}
Copy the code

This find function does the following: 1. Finds the root of node x and returns — finds the root node. Find (x) = find(x); find(x) = find(x); And then we find the root of 4. The second step may be a bit around, want to stress is that compressed path is and check on the time complexity of optimization, it will change the structure of a tree, the figure below shows, but can save time, above 5 and 4, if not compressed path, so every 5 to find 4 for three times, but after using compressed path optimization, starting from the second, 5 for 4 only once, Look at the picture more obvious! Take figure 1 above for example. After the second step, Figure 1 becomes the following:

Figure 2

Here is the mix function:

void mix(int x, int y) // connect x, y (change parent of x to parent of y or vice versa)
{
    int fux = find(x); // Find the parent of x, fux.
    int fuy = find(y);
    if(fux ! = fuy)// If x and y do not belong to the same parent connected x, y
        //pre[fux] = fuy; / / 1
        pre[fuy] = fux;   / / 2
        
}
Copy the code

What this function does is very simple, it connects x,y. For example in figure 1, if you execute mix(1,6), figure 1 becomes the following:

Figure 3

Or is it

Figure 4.

Figure 3 and Figure 4 correspond to the //1 and //2 statements in the mix function code, respectively. They look a little bit different, but they both achieve the goal of connecting 1 and 6, and they’re both ultimately achievable and searchable.

Finally, look at the code in the main function:
int main(a)
{
    int n, m;
    while (cin >> n >> m)
    {
        int ans = 0;
        memset(t, 0.sizeof(t));
        if (n == 0)
            break;
        for (int i = 1; i <= n; i++) // Initialize the parent of all points as itself
            pre[i] = i;/ / 1
        for (int i = 1; i <= m; i++)
        {
            int a, b;
            cin >> a >> b;
            mix(a, b); // connect a to B
        }
        for (int i = 1; i <= n; i++)
        {
            t[find(i)] = 1; //2 marks all the parents
        }
        for (int i = 1; i <= n; i++)
            if (t[i])
                ans++; // Count the number of parent nodes
        cout << ans - 1 << endl;
    }
    return 0;
}
Copy the code

The //1 in the main function code initializes the parents of all towns to the nodes themselves, that is, to form a set of their own, which is essential, otherwise all towns have zero parents, which is obviously an error. At //2, mark the root of all nodes and sum them up

Insert two questions, which can be done as an exercise: cow and garlic

Solve the portal

Finally, post my HDUOJ1232AC code:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <algorithm>
using namespace std;
int pre[1005];  //pre[I] record the parent of I
int t[1005];    // Record all parent nodes
int find(int x) // find the root
{
    int r = x; // find the root of x, r
    while(pre[r] ! = r) r = pre[r];int temp, i;
    i = x;
    //* Compression path
    // Convert all nodes below root r to children of r.
    while(pre[i] ! = r) { temp = pre[i];//temp records the parent of I before changing it to the root of I.
        pre[i] = r;    // Change the parent of I to the root of I
        i = temp;      / / loop
    }
    return r; // The primary goal of find is to return the root of x
}
void mix(int x, int y) // connect x, y (change parent of x to parent of y or vice versa)
{
    int fux = find(x); // Find the parent of x, fux.
    int fuy = find(y);
    if(fux ! = fuy)// If x and y do not belong to the same parent connected x, y
        pre[fux] = fuy;
}

int main(a)
{
    int n, m;
    while (cin >> n)
    {
        int ans = 0;
        memset(t, 0.sizeof(t));
        if (n == 0)
            break;
        cin>>m;
        for (int i = 1; i <= n; i++) // Initialize the parent of all points as itself
            pre[i] = i;
        for (int i = 1; i <= m; i++)
        {
            int a, b;
            cin >> a >> b;
            mix(a, b); // connect a to B
        }
        for (int i = 1; i <= n; i++)
        {
            t[find(i)] = 1; // mark all the parents
        }
        for (int i = 1; i <= n; i++)
            if (t[i])
                ans++; // Count the number of parent nodes
        cout << ans - 1 << endl;
    }

    return 0;
}
Copy the code