Captain emoticons town building

Check and set

  • Can solve connectivity problems
  • Considering the average number of lookups, merging a tree with fewer nodes into a tree with more nodes leads to fewer average lookups

Connectivity problem

The quick – find algorithm

  • Based on the idea of coloring, all the dots are different colors at the beginning
  • The operation of joining two dots shows that dots of one color are dyed into another color
  • If two points are of the same color, they are connected, otherwise they are not
  • This method is called quick-find for parallel lookup sets.

Quick-find summary: Lookup is very fast (O(1)), merge is slow (O(n))

The quick – union algorithm

  • In tree-based data structures, the root node of all points is itself at the beginning
  • The operation of joining two points shows that the collection of one point is hung on the root node of the other point
  • If the two root nodes are the same, they are connected, otherwise they are not
  • This method is called the Quick-union algorithm of look-up sets.

Quick-union summary: Merge operation is fast, search operation is slow, connect operation and search operation are related to tree height. Is it most efficient if brainless attaches one set to another? If improved, is the merge reference based on the number of nodes or the height of the tree?

Demonstrate whether the improvement is based on the number of nodes or the height of the tree

Demonstration indicator: Average search times = Search times of all nodes/Total number of nodes Suppose that the number of nodes in a tree is SA, the depth of all nodes is added to la, the number of nodes in b tree is sb, and the depth of all nodes is added to lb when a B tree is mounted to a tree: Average search times = La +lb+sb/(sa+sb) When a tree is mounted to B tree: Average search times = La +lb+sa/(sa+sb

Weighted -quick- Union algorithm is optimized according to rank

  • Sets an array to record the number of nodes per node (set)
  • The connected operation judges the number of nodes in two sets, takes the set with smaller number as a subset, and changes the number of nodes in the set at the same time

Summary: Performance has improved a lot, but the tree structure of the collection is not important, and lookups are most efficient if all child nodes are hung on the root node

Weighted – Quick – Union algorithm for path compression

  • All child nodes are hung on the root node for lookup operations

Conclusion: Path compression efficiency is significantly improved, coding difficulty is low, compared with rank-by-rank optimization, cost-effective

Tear one by hand and check the set

class UnionSet {
    constructor(n) {
        this.fa = Array(n+1)
        this.size = Array(n+1).fill(1)
        for(let i = 0; i < n; i++) {
            this.fa[i] = i
        }
    }
    get(x) {
        if (this.fa[x] == x) return x
        const root = this.get(this.fa[x])
        this.fa[x] = root
        return root
    }
    marge(a, b) {
        let sa = this.get(a), sb = this.get(b)
        if (sa == sb) return
        if (this.size[sa] > this.size[sb]){
            this.fa[sb] = sa
            this.size[sa] += this.size[sb]
        } else {
            this.fa[sa] = sb
            this.size[sb] += this.size[sa]
        }
    }
}
// select * from * * *
class UnionSet {
    constructor(n) {
        this.fa = Array(n+1)
        for(let i = 0; i < n; i++) {
            this.fa[i] = i
        }
    }
    get(x) {
        return this.fa[x] = (this.fa[x] == x ? x : this.get(this.fa[x]))
    }
    marge(a, b) {
        this.fa[this.get(b)] = this.get(a)
    }
}
Copy the code

LeetCode liver problem

    1. Number of provinces
// The number of root nodes will be traversed (get returns value equal to itself)
var findCircleNum = function(isConnected) {
    const n = isConnected.length
    let u = new UnionSet(n), ans = 0
    for(let i = 0; i < n; i++) {
        for(let j = 0; j < i; j++) {
            if(isConnected[i][j]) u.marge(i,j)
        }
    }
    for(let i = 0; i < n; i++) {
        if (u.get(i) == i) ans++
    }
    return ans
};
Copy the code
    1. The number of islands
// Finally query the number of root nodes by connecting adjacent '1'
// Convert a two-dimensional array to a number, connect the corresponding position of the number
// Each '1' node only needs to connect the other '1' in both directions
var numIslands = function(grid) {
    let row = grid.length, col = grid[0].length, ans = 0
    let toIndex = function(i, j) {
        return i * col + j
    }
    let u = new UnionSet(row * col)
    for(let i = 0; i < row; i++) {
        for(let j = 0; j < col; j++) {
            if (grid[i][j] == '0') continue
            if (i > 0 && grid[i - 1][j] == '1') u.marge(toIndex(i, j), toIndex(i - 1, j))
            if (j > 0 && grid[i][j - 1] = ='1') u.marge(toIndex(i, j), toIndex(i, j - 1))}}for(let i = 0; i < row; i++) {
        for(let j = 0; j < col; j++) {
            if (grid[i][j] == '1' && u.get(toIndex(i, j)) == toIndex(i, j)) ans++
        }
    }
    return ans
};
Copy the code
    1. The satisfiability of an equation
// Connect equal letters. If unequal letters are connected, the equation cannot be satisfied
var charToIndex = function(s) {
    return s.charCodeAt() - 97
}
var equationsPossible = function(equations) {
    let u = new UnionSet(26)
    for(item of equations) {
        if (item[1] = ='! ') continue
        u.marge(charToIndex(item[0]), charToIndex(item[3))}for(item of equations) {
        if (item[1] = ='! ' && u.get(charToIndex(item[0])) == u.get(charToIndex(item[3))) {return false}}return true
};
Copy the code
    1. Redundant links
// If the connection is redundant, then the current two points must be connected
var findRedundantConnection = function(edges) {
    let u = new UnionSet(edges.length)
    for(let item of edges) {
        if (u.get(item[0]) == u.get(item[1])) return item
        u.marge(item[0], item[1])}return[]}.Copy the code
    1. Number of network connection operations
// If the number of cables is less than the number of computers -1, it indicates that the number of cables is insufficient. Return -1
// Connect the connected computer, and finally count the number of modules
var makeConnected = function(n, connections) {
    if (connections.length < n - 1) return -1
    let u = new UnionSet(n), ans = 0
    for(let item of connections) {
        u.marge(item[0], item[1])}for(let i = 0; i < n; i++) {
        if (u.get(i) == i) ans++
    }
    return ans - 1
};
Copy the code
    1. Longest continuous sequence
// Increase the number of elements in the current set
// Define a map current value and subscript. If there is a current value -1 and a current value +1, connect the subscript of the current value with the subscript of -1 and +1
// Finally returns the largest number of elements in the collection
class UnionSet {
    constructor(n) {
        this.fa = Array(n + 1)
        this.cut = Array(n + 1).fill(1)
        for(let i = 0; i < n; i++) {
            this.fa[i] = i
        }
    }
    get(x) {
        return this.fa[x] = (this.fa[x] == x ? x : this.get(this.fa[x]))
    }
    marge(a, b) {
        let sa = this.get(a), sb = this.get(b)
        if (sa == sb) return
        this.cut[sa] += this.cut[sb]
        this.fa[sb] = sa
    }
}
var longestConsecutive = function(nums) {
    let u = new UnionSet(nums.length), map = {}, ans = 0
    for(let i = 0; i < nums.length; i++) {
        if (map[nums[i]] >= 0) continue
        if (map[nums[i] - 1] > =0) {
            u.marge(i, map[nums[i] - 1])}if (map[nums[i] + 1] > =0) {
            u.marge(i, map[nums[i] + 1])
        }
        map[nums[i]] = i
    }
    for(let i = 0; i < nums.length; i++) {
        if (u.get(i) == i && u.cut[i] > ans) ans = u.cut[i]
    }
    return ans
};
Copy the code
    1. Remove the most stones in a row or row
// Connect stones in the same row or column. The number of stones left is equal to the number of sets
// The maximum number of stones that can be removed is the total number of stones minus the set number
var removeStones = function(stones) {
    let u = new UnionSet(stones.length), num = 0, map_x = {}, map_y = {}
    for(let i = 0; i < stones.length; i++) {
        let x = stones[i][0]
        let y = stones[i][1]
        if (map_x[x] >= 0) {
            u.marge(i, map_x[x])
        }
        if (map_y[y] >= 0) {
            u.marge(i, map_y[y])
        }
        map_x[x] = i
        map_y[y] = i
    }
    for(let i = 0; i <= stones.length; i++) {
        if (u.get(i) == i) num++
    }

    return stones.length - num
};
Copy the code
    1. Exchange elements in a string
Order the connectable characters from smallest to largest
// Connect the subscripts corresponding to all letters
// Define a map, connect each set root node as the key, build the small top heap
// Fetch the top element from the small top heap of the root node of the current element
var smallestStringWithSwaps = function(s, pairs) {
    let u = new UnionSet(s.length), queueMap = {}, ans = ' '
    const h = new MinPriorityQueue();
    for(item of pairs) {
        u.marge(item[0], item[1])}for(let i = 0; i < s.length; i++) {
        let root = u.get(i)
        if(queueMap[root]) queueMap[root].enqueue(s[i])
        else {
            queueMap[root] = new MinPriorityQueue({
                priority: (item) = > item.charCodeAt()
            })
            queueMap[root].enqueue(s[i])
        }
    }
    for(let i = 0; i < s.length; i++) {
        ans += queueMap[u.get(i)].dequeue().element
    }
    return ans
};
Copy the code
    1. Account merge
var accountsMerge = function(accounts) {
    // Create two maps for mailboxes: coordinates, mailboxes: names
    let emailToIndex = new Map(), emailToName = new Map(), emailCut = 0
    for(let item of accounts) {
        const name = item[0]
        for(let i = 1; i < item.length; i++) {
            const email = item[i]
            if(! emailToIndex.has(email)) { emailToIndex.set(email, emailCut++) emailToName.set(email, name) } } }// Connect each non-repeating mailbox as a collection
    let u = new UnionSet(emailCut)
    for(let item of accounts) {
        const emailName = item[1]
        const emailIndex = emailToIndex.get(emailName)
        for(let i = 1; i < item.length; i++) {
            u.marge(emailIndex, emailToIndex.get(item[i]))
        }
    }
    // Create a mailbox root node: a map of mailboxes
    const indexToEmail = new Map(a)for(item of emailToIndex.keys()) {
        const index = u.get(emailToIndex.get(item))
        const account = indexToEmail.get(index) ? indexToEmail.get(index) : []
        account.push(item)
        indexToEmail.set(index, account)
    }
    // Merge accounts
    const merged = []
    for(let item of indexToEmail.values()) {
        item.sort()
        const name = emailToName.get(item[0])
        constaccount = [] account.push(name) account.push(... item) merged.push(account) }return merged
};
Copy the code