Union search algorithm

Posted on Edited on In Waline:

First, the topic of the previous leetcode: https://leetcode-cn.com/problems/satisfiability-of-equality-equations/

After we see this problem, it is very easy to think about it is to first find a data structure to save all equal relations, and then judge whether the two sides of the inequality exist in the structure at the same time.

The first step in this process is the union set, put the relevant data in a set, the second step is to find, find whether the correlation is established in this set, this search process can be optimized, that is, the union Set search path compression. Recommend this blog: https://blog.csdn.net/liujian20150808/article/details/50848646

Algorithm

The set is represented by an element of the set, which is called the’representative element 'of the set.
All elements in a set are organized into a tree structure rooted in the representative element.
For each element parent [x] refers to the parent node of x in the tree structure. If x is the root node, let parent [x] = x.
For the lookup operation, suppose you need to determine the set where x is located, that is, determine the representative element of the set. You can continuously move up the tree structure along parent [x] until you reach the root node.

1
To determine whether two elements belong to the same set, we only need to see whether their representative elements are the same.

Path compression

1
2
3
In order to speed up the search speed, the parent of all points on the path from x to the root node is set as the root node when searching. This optimization method is called compressed path.

After using this optimization, the average complexity can be regarded as the inverse function of the Ackerman function, which can be roughly considered a constant in practical applications.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
Path compression while searching
var find = function (parent, index) {
    index = index.charCodeAt() - 97;
    while(parent[index] != index) {
        parent[index] = parent[parent[index]];
        index = parent[index];
    }
    return index;
}

//update union
var union = function (parent, index1, index2) {
    parent[find(parent, index1)] = find(parent, index2);
}

var equationsPossible = function(equations) {
    let parent = [];
    //initialize union
    for (let i = 0; i < 26; i++) {
        parent[i] = i;
    }
    Generate a union according to the equation
    for (let i = 0; i < equations.length; i++) {
        if (equations[i].indexOf('')  1) {
            const variables = equations[i].split('');
            union(parent, variables[0], variables[1]);
        }
    }
    //Sequentially search according to the inequality
    for (let i = 0; i < equations.length; i++) {
        if (equations[i].indexOf('!=')  1) {
            const variables = equations[i].split('!=');
            if (find(parent, variables[0])  find(parent, variables[1])) {
                return false
            }
        }
    }
    return true;
};

Usage scenarios

From my current understanding, and lookup sets apply to the case of ** dividing a set of data into blocks of interconnected data **, such as the above, dividing all data into blocks of data sets according to an equality relationship, each The data inside the dataset is equal.

Example 1

https://leetcode-cn.com/problems/redundant-connection/

In a tree, the number of edges is 11 less than the number of nodes. If a tree has NN nodes, then the tree has N-1N − 1 edges. The graph in this problem has an additional edge on top of the tree, so the number of edges is also NN.

A tree is a connected and acyclic undirected graph. After adding an additional edge to the tree, a ring will appear, so the additional edge is the edge that causes the ring to appear.

Additional edges can be found through the union lookup set. 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 traversing to the current edge, so the current edge will not cause a ring to appear, merging the connected components of the two vertices.

  • If two vertices belong to the same connected component, it means that the two vertices have been connected before traversing to the current edge, so the current edge causes a ring to appear, for the additional edge, returning the current edge as the answer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
var findRedundantConnection = function(edges) {
    const nodesCount = edges.length;
    const parent = new Array(nodesCount + 1).fill(0).map((value, index) => index);
    for (let i = 0; i < nodesCount; i++) {
        const edge = edges[i];
        const node1 = edge[0], node2 = edge[1];
        if (find(parent, node1) != find(parent, node2)) {
            union(parent, node1, node2);
        } else {
            return edge;
        }
    }
    return [0];
};

const union = (parent, index1, index2) => {
    parent[find(parent, index1)] = find(parent, index2);
}

const find = (parent, index) => {
    while(parent[index] ! index) {
        parent[index] = parent[parent[index]];
        index = parent[index];
    }
    return index;
}

Example 2

https://leetcode-cn.com/problems/most-stones-removed-with-same-row-or-column/

According to the rule that stones can be removed: if there are other stones on the same line or column of a stone, then the stone can be removed. It can be found that all vertices in a connected graph must be deleted according to this rule to only one vertex left.

Why do you say that? Since these vertices are in a connected graph, you can traverse all the vertices of the connected graph by traversing (depth-first traversal or breadth-first traversal). Then you can remove the stone in reverse according to the traversal method, and finally only one stone is left. So: the maximum number of stones that can be removed = the number of all stones - the number of connected components.

The question does not ask us to give a specific plan to remove the stone, which can be considered and collected.

** And check how to distinguish the abscissa and ordinate in the collection **
However, we will encounter such a problem: the position of the stone is "ordered number pair (two-dimensional) ", and the bottom of the search set is “one-dimensional array”. How should we distinguish the abscissa and ordinate in the search set?
, you can map one of the coordinates to another interval that does not coincide with [0, 10000], you can do it by subtracting all 10001 or adding all 10001 to the abscissa

In the union search set, we need to maintain the number of connected components. When creating a new vertex, the connected component is added 11; when merging two not in the same connected component and search set, the connected component is subtracted 11.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
var removeStones = function(stones) {
    const parent = new Map();
    let count = 0;
    const find = function(x) {
        if (!parent.has(x)) {
            parent.set(x, x);
            count++;
        }
        if (parent.get(x) != x) {
            parent.set(x, find(parent.get(x)));
        }
        return parent.get(x);
    }
    const union = function(x, y) {
        const rootX = find(x);
        const rootY = find(y);
        if (rootX ! rootY) {
            parent.set(rootX, rootY);
            count--;
        }
    }
    stones.forEach((stone) => {
        union(stone[0] + 10001, stone[1]);
    })
    return stones.length - count;
};