[Daily Algorithm] Union lookup data structure and its examples — day15

[Daily Algorithm] Union lookup data structure [and] its examples — day15

✨Blogger introduction

[💂 Personal homepage: Suzhou Program Dabai]

[💂 Personal community: CSDN programmers all over the country]

🤟Introduction to the author: Member of China DBA Alliance (ACDU), administrator of CSDN programmers (women) gathering places across the country. Currently engaged in the development of industrial automation software. Good at C#, Java, machine vision, underlying algorithms and other languages. Qiyue Software Studio will be established in 2019, and Suzhou Kaijie Intelligent Technology Co., Ltd. will be registered in 2021

💅 If you have any questions, please send a private message, we will reply in time

👤 WeChat account: stbsl6, WeChat public account: Suzhou Program Dabai

💬If the article is helpful to you, welcome to follow, like, and favorite (one-click three links)

🎯 If you want to join the technical exchange group, you can add me as a friend, and the group will share learning materials

and check

Union lookup is one of the concise and elegant [data structures] , mainly used to solve the problem of grouping some elements. It manages a series of disjoint sets and supports two operations:

  • Union: Combines two disjoint sets into one set.

  • Query (Find): Query whether two elements are in the same set.

data structure

The important idea of ​​union search is to use an element in the set to represent the set .

If the set is likened to a gang, and the representative element is the gang leader, let’s use this metaphor to see how the collection works.
In the beginning, all heroes fought their own way. Their respective leaders are naturally themselves. (For a set with only one element, the representative element is naturally the only one)
Now No. 2 wants to compete with No. 3 (merge the set that No. 3 and No. 2 are in), but No. 3 says, don’t fight me, let me help the Lord clean you up (merge the representative elements). Let’s assume that No. 1 wins again this time, so No. 2 also recognizes No. 1 as the leader.

Now let’s assume that No. 4, 5, and 6 also have some gang mergers, and the situation in the rivers and lakes becomes as follows:
Now suppose that No. 2 wants to compete with No. 6. Just like what I just said, call the leader No. 1 and No. 4 to come out and fight (the leader is really hard). After No. 1’s victory, No. 4 recognized No. 1 as the gang leader, and of course his subordinates also surrendered.
To sum up, the union search set is a tree-like structure. To find the representative element of the set, you only need to visit the parent node (the circle indicated by the arrow in the figure ) layer by layer, and go directly to the root node of the tree. (the orange circle in the picture)**. The parent of the root node is itself. We can directly draw it as a tree:

Data structure core code

Init

If there are n elements numbered 1, 2, 3, …, n, we use an array fa[] to store the parent of each element (this works because each element has one and only one parent) ). To start, let’s make their parent nodes themselves.

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

Find

We use recursive writing to realize the query of the representative element: visit the parent node layer by layer until the root node (the root node’s sign is that the parent node is itself) . To determine whether two elements belong to the same set, just look at whether their root nodes are the same.

Note: This query algorithm has an optimization scheme, see below.

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

Union

The merging operation is also very simple, first find the representative elements of the two sets, and then set the parent node of the former to the latter. For example, the following code is i gang join j gang.

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

Find(Optimized)

Since we only care about the root node corresponding to an element, we want the path from each element to the root node to be as short as possible, preferably only one step. We can optimize the merge to prevent the formation of overly long paths.

Path compression: As long as we set the parent node of each node along the way as the root node during the query process.

Compared:

int find(int x)
{
    return x == fa[x] ? x : (fa[x] = find(fa[x]));
}

For good looks, the above code is equivalent to:

int find(int x)
{
    if(x == fa[x])
        return x;
    else{
        fa[x] = find(fa[x]);   //The parent node is set as the root node 
        return fa[x];          //Return the parent node
    }
}

example

Pointing to Offer II 118. Extra edge

A tree can be viewed as a connected and acyclic undirected graph.

Given a graph after adding an edge to a tree of n nodes (node ​​values ​​1~n). The two vertices of the added edge are contained between 1 and n, and the added edge does not belong to an existing edge in the tree. The information of the graph is recorded in the two-dimensional array edges of length n, and edges[i] = [ai, bi] means that there is an edge between ai and bi in the graph.

Find an edge that can be deleted so that the remainder is a tree with n nodes. If there are multiple answers, returns the last edge in the array edges.

Input: edges = [[1,2],[1,3],[2,3]] 
Output: [2,3]

answer:

In a tree, the number of edges is 1 less than the number of nodes. If a tree has n nodes, then the tree has n-1 edges. The graph in this question has one more edge on the tree, so the number of edges is also n.

A tree is a connected and acyclic undirected graph, and a cycle will appear after an edge is added to the tree, so the excess edge is the edge that causes the cycle to appear.

You can find redundant edges by union search. Initially, each node belongs to a different connected component. Traverse each edge to determine whether the two vertices connected by this edge belong to the same connected component.

If two vertices belong to different connected components, it means that the two vertices are not connected before the current edge is traversed, so the current edge will not cause a ring to appear, and the connected components of these two vertices are merged.

If two vertices belong to the same connected component, it means that the two vertices are already connected before traversing to the current edge, so the current edge causes a ring to appear, which is a redundant edge, and the current edge is returned as the answer.

class  Solution {
     int [] p;
     //Query the root node father 
    int  find ( int x ) {
         return p[x]==x ? x : (p[x]=find(p[x]));
    }
    //Connect two nodes, identify b's father as the new father 
    void  union ( int a, int b ) {
        p[find(a)] = find(b);
    }
    //To determine whether the two nodes are connected, and whether they are the same father 
    boolean query ( int a, int b ) {
         return find(a) == find(b);
    }
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        p = new  int [n+ 1 ];
         //Initialize and check the set, first consider yourself a father 
        for ( int i= 0 ;i<=n;i++) p[i] = i;
         for ( int [] e : edges){
             if (query(e[ 0 ], e[ 1 ])) return e;
             else union(e[ 0 ], e[ 1 ]);
        }
        return null;
    }
}

💫Click on the direct data to receive💫

❤️Follow Suzhou program Dabai public account ❤️

👇 👇👇

Leave a Comment

Your email address will not be published. Required fields are marked *