“This is my 36th day of participating in the First Challenge 2022. For details: First Challenge 2022.”

First, and look up the definition of the set

And look up the definition of set:

  1. There are several samples A, B, C, D… The type hypothesis is V

  2. In the parallel set, you start off thinking that each sample is in a separate set

  3. The user can call the following two methods at any time:

    • Boolean isSameSet(V x, V y) : Query whether sample x and sample y belong to a set

    • Void union(V x, V y) : Combine all samples of the respective sets of x and y into one set

  4. The isSameSet and Union methods are as cheap as possible

Two, and look up the characteristics of the set

  1. Each node has a pointer pointing upwards
  2. The head node found above node A is called the representative node of the set in which a is located
  3. Query whether x and y belong to the same set, is to see if the found representative node is the same
  4. To combine all the points in the respective sets of x and y into one set, all that is required is for the representative point of the small set to hang below the representative point of the large set

Third, and the optimization of the search set

  1. The process of a node moving up to its representative point flattens the chain along the way
  2. The smaller set hangs below the larger set
  3. If the method is called frequently, the cost of a single call is O(1), which is true for both methods

Fourth, and the application of search set

  1. Solve the merging problem of two large areas
  2. Often used in fields such as graphs

Fifth, and the implementation of the search set

public static class Node<V> {
    V value;

    public Node(V v) { value = v; }}public static class UnionFind<V> {
    public HashMap<V, Node<V>> nodes;
    public HashMap<Node<V>, Node<V>> parents;
    public HashMap<Node<V>, Integer> sizeMap;

    public UnionFind(List<V> values) {
        nodes = new HashMap<>();
        parents = new HashMap<>();
        sizeMap = new HashMap<>();
        for (V cur : values) {
            Node<V> node = new Node<>(cur);
            nodes.put(cur, node);
            parents.put(node, node);
            sizeMap.put(node, 1); }}// You are given a node, please go up to no further, return the representative
    private Node<V> findFather(Node<V> cur) {
        Stack<Node<V>> path = new Stack<>();
        while(cur ! = parents.get(cur)) { path.push(cur); cur = parents.get(cur); }while(! path.isEmpty()) { parents.put(path.pop(), cur); }return cur;
    }

    // Whether in the same set
    public boolean isSameSet(V a, V b) {
        return findFather(nodes.get(a)) == findFather(nodes.get(b));
    }

    // Merge two sets
    public void union(V a, V b) {
        Node<V> aHead = findFather(nodes.get(a));
        Node<V> bHead = findFather(nodes.get(b));
        if(aHead ! = bHead) {int aSetSize = sizeMap.get(aHead);
            intbSetSize = sizeMap.get(bHead); Node<V> big = aSetSize >= bSetSize ? aHead : bHead; Node<V> small = big == aHead ? bHead : aHead; parents.put(small, big); sizeMap.put(big, aSetSize + bSetSize); sizeMap.remove(small); }}public int sets(a) {
        returnsizeMap.size(); }}Copy the code

Six, and check the summary of the set

The essence is to take the representative node to determine which set it belongs to

And look up the set of 3 hashmaps

  • The sample corresponds to its wrapped circle: HashMap

    > Nodes
    ,node

  • Instead of adding Pointers to Node, use HashMap to map the Node to its parents: HashMap

    ,Node

    > parents

  • SizeMap: HashMap<

    ,Integer> sizeMap, key: head Node, only records representing the Node are left

Why do small hang big? Reduce the number of hangs when the parallel search set chain becomes flat