preface

Joint search set is a data structure
Union, representing merger
Find represents search
Set represents a data structure based on a dictionary. Its basic function is to merge the elements in the set and find the elements in the set
definition:
Join search set is a tree data structure, which is used to deal with the merging and query of some disjoint sets (the so-called join and search). For example, we can use union search to judge how many trees there are in a forest and whether a node belongs to a tree.

Main composition:
The union search set is mainly composed of an integer array pre[] and two functions find(), join().
Array pre[] records who the precursor node of each point is. The function find(x) is used to find which set the specified node x belongs to, and the function join(x,y) is used to merge two nodes X and y.

effect:
The main function of joint search set is to find the number of connected branches (if all points in a graph have reachable relations (directly or indirectly connected), then the number of connected branches of this graph is 1; If this graph has two subgraphs reachable to each other, then the number of connected branches of this graph is 2...)

find() function

We need to define an array: int pre[1000]; (the length of the array depends on the meaning of the question). This array records who is the precursor node of each element. For example, pre[16]=6 means that the precursor node of element 16 is number 6. If the precursor node of an element is itself, it means that it represents the element. This is the end of the search. There is also an element that forms a set, so the representative element of this set is itself.

int find(int x)					//Find the delegate of x
{
	while(pre[x] != x)			//If the precursor node of x is not itself
		x = pre[x];
	return x;
}

join function

The function of join is to merge two sets. The key to merging two sets is to find the representative elements of two sets, and take one of them as the precursor node of the other.

void join(int x,int y)                     
{
    int fx=find(x), fy=find(y); 
    if(fx != fy) 
        pre[fx]=fy;	//fy is the precursor node of fx
}

1, Number of provinces

Increase the number of sets by one during initialization
Reduce the number of sets by one when merging
So we need to add an extra variable in the template to track the number of sets (how many trees there are).

class UnionFind{
public:
    int find(int x){
        int root = x;
        
        while(father[root] != -1){
            root = father[root];
        }
        
        while(x != root){
            int original_father = father[x];
            father[x] = root;
            x = original_father;
        }
        
        return root;
    }
    
    bool is_connected(int x,int y){
        return find(x) == find(y);
    }
    
    void merge(int x,int y){
        int root_x = find(x);
        int root_y = find(y);
        
        if(root_x != root_y){
            father[root_x] = root_y;
            num_of_sets--;
        }
    }
    
    void add(int x){
        if(!father.count(x)){
            father[x] = -1;
            num_of_sets++;
        }
    }
    
    int get_num_of_sets(){
        return num_of_sets;
    }
    
private:
    // Record parent node
    unordered_map<int,int> father;
    // Number of record sets
    int num_of_sets = 0;
};

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        UnionFind uf;
        for(int i = 0;i < isConnected.size();i++){
            uf.add(i);
            for(int j = 0;j < i;j++){
                if(isConnected[i][j]){
                    uf.merge(i,j);
                }
            }
        }
        
        return uf.get_num_of_sets();
    }
};

 

2, Redundant links

Divine

class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        vector<int> rp(1001);
        int sz = edges.size();
        // Initialize each element as a separate set, and the representative node is itself
        for(int i=0;i<sz;i++)
            rp[i] = i;
        for(int j=0;j<sz;j++){
            // Find the representative node of the set of two nodes on the edge
            int set1 = find(edges[j][0], rp);
            int set2 = find(edges[j][1], rp);
            if(set1 == set2)  // The two sets represent the same node, indicating that there is a ring and the answer is returned
                return edges[j]; 
            else    // Two sets are independent and merged. Stamp the previous set representative node onto the next set representative node
                rp[set1] = set2;
        }
        return {0, 0};
    }

    // To find the path and return the representative node is actually to return the representative node of the set where the node is located given the current node
    // The compressed path written here before causes ambiguity, because the result is not updated to the vector, so it is more appropriate to change it to path search here
    // Thank you for your proposal
    int find(int n, vector<int> &rp){
        int num = n;
        while(rp[num] != num)
            num = rp[num];
        return num;
    }
};
 

summary

The future will be bright, and luck is on the way!