May brush question 26 - concurrent search

Today's brush topic content ： Union checking set

Preface

• An algorithm opens the way to brush the questions of waste materials , Update the problem solution content of the problem brush every day
• Focus on personal understanding , Look at the difficulty and update the number of questions
• The title comes from Li Kou
• New column , Try to work out at least one question every day =v=
• Language java、python、c\c++

---

One 、 Today's topic

I only finished one question today , There's not much time left , Make up the rest another day

1. 990. The satisfiability of equation
2. 1319. The number of connected network operations
3. 886. Possible dichotomy

Two 、 Their thinking

1. 990. The satisfiability of equation

1. Use and search set to put all == The characters of fall into one category
2. lookup != Whether the characters of belong to the same class
3. If existence belongs to a class , It shows that these two characters already belong to the equation , return false, Otherwise true

class Solution {
    
    int N = 256;
    int[] fset;
    //  Initialize and query set , Use characters to store 
    public void init(){
    
        fset = new int[N];
        for(int i=0; i < N; i++){
    
            fset[i] = i;
        }
    }
    
    //  Find which set it belongs to 
    public int find(int x){
    
        if (x == fset[x]){
    
            return x;
        }else{
    
            //  Set the parent node of the nodes along the way as the root node 
            fset[x] = find(fset[x]);
            return fset[x];
        }
    }
    //  Merge sets 
    public boolean merge(int x, int y){
    
        int rx = find(x);
        int ry = find(y);
        if (rx != ry){
    
            fset[rx] = ry;
            return false;
        }
        return true;
    }
    
    public boolean equationsPossible(String[] equations) {
    
        int n = equations.length;
        init();
        //  Merge two characters equally into a set 
        for (String e: equations){
    
            if (e.charAt(1) == '='){
    
                merge(e.charAt(0), e.charAt(3));
            }
        }
        //  If these two characters are already in the same set , It also appears in the equation ！, The explanation must be false 
        for(String e: equations){
    
            if (e.charAt(1) == '!'){
    
                if ( find(e.charAt(0)) == find(e.charAt(3)) ){
    
                    return false;
                }
            }
        }
        
        return true;
    }
}

/* *  Use and look up sets , Only when all equations belong to a set can the problem condition be satisfied  */

---

2. 1319. The number of connected network operations

Adopt simple method and path compression to solve the problem
Path compression and search set related view this article Union checking set

1. This question , Using the simple method of searching sets
2. Combine all connected computers
3. Counting the number of all sets , Count all sets -1 That's the answer.

The simple code is as follows ：

class Solution {
    
    int[] fset;
    int N;
    /* *  Initialize and query set  */
    public void init(int n){
    
        fset = new int[n];
        int i;
        for(i = 0; i < n; i++){
    
            fset[i] = i;
        }
    }
    
    /* *  lookup x Which set does it belong to  */
    public int find(int x){
    
        return fset[x];
    }
    
    /* *  Merge two sets  */
    public void merge(int x, int y){
    
        int rx = find(x);
        int ry = find(y);
        //  Find the set to which they belong , If different sets , Then merge the two 
        if (rx != ry){
    
            for (int i = 0; i < N; i++){
    
                if (fset[i] == ry){
    
                    fset[i] = rx;
                }
            }
        }
    }
    
    public int makeConnected(int n, int[][] connections) {
    
        int m = connections.length;
        int i;
        N = n;
        if(m < n - 1){
    
            return - 1;  // n Computers , Need at least n-1 Cables 
        }
        init(n);  //  initialization 
        int count = 0;
        int[] hash = new int[n];
        for(int[] nums: connections){
    
            merge(nums[0], nums[1]);  //  Merge two connected computers 
        }
        for(i = 0 ; i < n; i++){
    
            int setId = find(i);
            if (hash[setId] == 0){
    
                hash[setId]++;
                count++;
            }
        }
        return count - 1;
        // System.out.println(fset[3]);
    }
}

/* n Computers , Need at least n-1 Table cable   Calculate the number of computers belonging to the same set   Finding out the number of independent computers that do not belong to a set is the answer  */

The path compression code is as follows ：

class Solution {
    
    int[] fset;
    int N;
    /* *  Initialize and query set  */
    public void init(int n){
    
        fset = new int[n];
        int i;
        for(i = 0; i < n; i++){
    
            fset[i] = i;
        }
    }
    
    /* *  lookup x Which set does it belong to , And set the parent nodes of the points on the path to rx */
    public int find(int x){
    
        if (x == fset[x]){
    
            return x;
        }else{
    
            fset[x] = find(fset[x]);
            return fset[x];
        }
    }
    
    /* *  Merge two sets ？？？ */
    public boolean merge(int x, int y){
    
        int rx = find(x);
        int ry = find(y);
        //  Find the set to which they belong , If different sets , Then merge the two 
        if (rx != ry){
    
            fset[rx] = ry;
            return true;
        }
        return false;
    }
    
    public int makeConnected(int n, int[][] connections) {
    
        int m = connections.length;
        int i;
        N = n;
        if(m < n - 1){
    
            return - 1;  // n Computers , Need at least n-1 Cables 
        }
        init(n);  //  initialization 
        int count = 0;
        int[] hash = new int[n];
        for(int[] nums: connections){
    
            merge(nums[0], nums[1]);  //  Merge two connected computers 
        }
        for(i = 0 ; i < n; i++){
    
            int setId = find(i);
            if (hash[setId] == 0){
    
                hash[setId]++;
                count++;
            }
        }
        return count - 1;
        // System.out.println(fset[3]);
    }
}

/* n Computers , Need at least n-1 Table cable   Calculate the number of computers belonging to the same set   Finding out the number of independent computers that do not belong to a set is the answer  */

---

3. 886. Possible dichotomy