To collate a collection is to combine something that is not originally in a collection into a collection. Not much use in real world scenarios.

In addition to cases where you need to query several collections at once, avoid the situation of querying multiple collections together.

The following is a simple implementation of an example to illustrate what a set of union lookup is, and exactly what the problem is solved by a set of union lookup.

Code parsing

package com.chaojilaji.book.andcheck;

public class AndCheckSet {


    public static Integer getFather(int[] father, int u) {
        if(father[u] ! = u) { father[u] = getFather(father, father[u]); }return father[u];
    }

    public static void join(int[] father,int x, int y) {
        int fx = getFather(father,x);
        int fy = getFather(father,y);
        if (fx != fy){
            father[fx] = fy;
        }
    }

    public static void main(String[] args) {
        int n = 10;
        int[] a = new int[n];
        for (int i = 0; i<n; i++){ a[i] = i;// Initialize one hundred collections
        }
        for (int i=0; i<n; i++){ System.out.println(i+""+getFather(a, i)); // For each collection, the parent node is itself}}}Copy the code

First, we define two functions, getFather and Join, to get the root of the collection where u resides and to merge the two collections, respectively. Let’s start with the getFather method

public static Integer getFather(int[] father, int u) {
    if(father[u] ! = u) { father[u] = getFather(father, father[u]); }return father[u];
}
Copy the code

I’m going to find out what the root of the set of u is. Generally speaking, if father[u] is equal to u itself, it indicates that the node where U is located is the root node, and this algorithm does not exit until it is equal. In other words, father of each node from U to the root node is directly set as the root node, and the root node of the current node is returned.

Then look at the join method

public static void join(int[] father,int x, int y) {
    int fx = getFather(father,x);
    int fy = getFather(father,y);
    if (fx != fy){
        father[fx] = fy;
    }
}
Copy the code

Find the root node of the set where x and Y nodes are located. If the root nodes are different, set father node of one node to another node, so as to merge into a set.

Application code

public static void main(String[] args) {
    int n = 10;
    int[] a = new int[n];
    for (int i = 0; i<n; i++){ a[i] = i;// Initialize n sets
    }
    for (int i=0; i<n; i++){ System.out.println(i+""+getFather(a, i)); // For each collection, the parent node is itself
    }
    System.out.println("-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --");
    join(a,0.1); // merge 0 and 1
    for (int i=0; i<n; i++){ System.out.println(i+""+getFather(a, i));
    }
    // By merging 0 and 1, the set becomes 9. The root of node 0 and 1 is node 1
    System.out.println("-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --");
    join(a,2.3); // merge 2 and 3
    for (int i=0; i<n; i++){ System.out.println(i+""+getFather(a, i));
    }
    // By merging 2 and 3, the set becomes 8. The root of node 2 and 3 is node 3
    System.out.println("-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --");
    join(a,1.3); // merge 1 and 3
    for (int i=0; i<n; i++){ System.out.println(i+""+getFather(a, i));
    }
    // The root of nodes 0,1,2, and 3 is node 3
}
Copy the code

First of all, we define n sets, n sets of values between 0 and n minus 1, and then their parents are all equal to themselves, so this is n independent sets, and the result is as follows

The parent of 0 is 0, the parent of 1 is 1, the parent of 2 is 2, the parent of 3 is 3, the parent of 4 is 5, the parent of 6 is 6, the parent of 7 is 7, the parent of 8 is 8, the parent of 9 is 9

Then call join(a,0,1) to merge 0 set and 1 set, and output the parent set of node

The parent of 0 is 1, the parent of 1 is 1, the parent of 2 is 2, the parent of 3 is 3, the parent of 4 is 5, the parent of 6 is 6, the parent of 7 is 7, the parent of 8 is 8, the parent of 9 is 9

As you can see, by merging 0 and 1, the set becomes 9, and the roots of both node 0 and node 1 are node 1. Then call join(a,2,3) to merge set 2 and set 3, and output the parent set of nodes

The parent of 0 is 1, the parent of 1 is 1, the parent of 2 is 3, the parent of 3 is 4, the parent of 4 is 5, the parent of 6 is 6, the parent of 7 is 7, the parent of 8 is 8, the parent of 9 is 9

As you can see, by merging 2 and 3, the set becomes 8, and both nodes 2 and 3 have roots of node 3. Finally, we call join(a,1,3) to merge set 1 and set 3, and output the parent set of nodes

The parent of 0 is 3, the parent of 1 is 3, the parent of 2 is 3, the parent of 3 is 3, the parent of 4 is 4, the parent of 5 is 5, the parent of 6 is 6, the parent of 7 is 7, the parent of 8 is 8, the parent of 9 is 9

As you can see, by merging 1 and 3, the set becomes 7, and the roots of nodes 0,1,2, and 3 are node 3.

The practical application

Code level, and lookup set is very easy to implement. However, we can also see that the application scenarios seem very limited. First, we need to define an array for father[x] = x, and then we can merge. It seems hard to think of application scenarios.

So we can imagine a scenario where we have a network topology of n and network devices, and we give you the connections between these N devices, and we ask you how many local networks there are. For this problem, we can first define each device to be connected to itself, and then join the two devices every time an edge appears. Finally, after traversing all nodes, we get how many different fathers, namely, how many different local unicom networks there are.

This problem can also be extended to our social circle. First of all, everyone is a separate collection, which generates connectivity in the process of getting to know people. Finally, it allows you to identify how many different people there are.

So you can see that this is essentially the number of connected blocks in graph theory.