What is a concurrent search set

And look up the set foundation

Any fool can read it and look it up

Union-find Sets (UNIon-find Sets) are tree-like data structures used for merging and querying disjoint Sets.

The idea of looking up a set is to use an array to represent the whole forest (parent), and the root node of the tree uniquely identifies a set. As long as we find the root of an element, we can determine which set it is in.

Basic operation

  1. Class creates a new and lookup set containing n single-element sets
  2. Unite (a, B) merges the two elements
  3. FindSet (index) finds the collection of an element

Path to the compression

In order to speed up the search, the parent of all points on the path from X to the root node is set as the root node during the search. This optimization method is called compression path.

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

Code implementation and lookup set

class UnionFind {
  constructor(n) {
    // Each node initializes its parent as itself
    this.parent = new Array(n).fill(0).map((item, index) = > index)
    // The number of sets on each node, initializing 1 itself
    this.rank = new Array(n).fill(1)
    // Several numbers, initialized to n
    this.setCount = n
  }
  // Quick lookup
  findSet(index) {
    if (this.parent[index] ! == index) {return this.findSet(this.parent[index])
    }
    return this.parent[index]
  }
  / / merge
  unite(a, b) {
    let root1 = this.findSet(a),
      root2 = this.findSet(b)
    if(root1 ! == root2) {if (this.rank[root1] < this.rank[root2]) {
        / / exchange
        [root1, root2] = [root2, root1]
      }
      // Merge the small onto the big
      this.parent[root2] = root1
      // Increase the number of collections on the node
      this.rank[root1] += this.rank[root2]
      // The total number of collections decreases
      this.setCount--
    }
  }
  // Returns the number of collections
  get count() {
    return this.setCount
  }
  // Whether the two nodes are connected
  connected(a, b) {
    let root1 = this.findSet(a),
      root2 = this.findSet(b)
    return root1 === root2
  }
}
Copy the code

Application of algorithm problems

547. Number of provinces

/ * * *@param {number[][]} isConnected
 * @return {number}* /
var findCircleNum = function(isConnected) {
  var n = isConnected.length
  var set = new UnionFind(n) // Create a new set
  for(var i = 0; i < n; i++) {
    for(var j = 0; j < n; j++) {
      var tmp = isConnected[i][j]
      if(i ! == j && tmp ===1) set.unite(i, j)
    }
  }
  return set.count // Returns the number of collections
};
Copy the code

684. Redundant connections

/ * * *@param {number[][]} edges
 * @return {number[]}* /
var findRedundantConnection = function(edges) {
  var n = edges.length
  var union = new UnionFind(n) // Create a new set
  var ans = null
  for(var i = 0; i < n; i++) {
    var tmp = edges[i]
    var node1 = tmp[0], node2 = tmp[1]
    If both nodes of an edge are already in the same set, the current edge can be removed
    if(union.findSet(node1) === union.findSet(node2)) ans = tmp
    // Merge two nodes
    union.unite(node1, node2)
  }
  return ans
};
Copy the code