DAY16 - 并查集

并查集是一种树状的结构，可以用来表示两个节点的连接、查询两个节点的连接~~
在刷题的时候有时候会使用到，就直接把并查集刻出来

class dsu{
public:
    unordered_map<int, int> arr;
    //找源头
    int find(int target){
        if(arr[target]==target){
            return target;
        }
        arr[target] = find(arr[target]);
        return arr[target];
    }
    //把b并进a
    void merge(int a, int b){
        int a_head = find(arr[a]);
        int b_head = find(arr[b]);
        arr[b] = a_head;
        return;
    }
};

上篇文章有提到，有时候会这样写(加权Union)(quick Union)

class dsu{
private:
    vector<int> arr;
    vector<int> ssize;
public:
    dsu(int n){
        arr.resize(n+1);
        ssize.resize(n+1);
        for(int i = 1; i<n+1; ++i){
            arr[i] = i;
            ssize[i] = 1;
        }
    }
    int find(int i){
        if(arr[i]==i){
            return i;
        }
        return find(arr[i]);
    }
    void merge(int a, int b){
        int a_head = find(a);
        int b_head = find(b);
        if(a_head!=b_head){
            if(ssize[a_head]>ssize[b_head]){//a较大
                arr[b_head] = a_head; //b并进a
                ssize[a_head]+=ssize[b_head];
            }
            else{
                arr[a_head] = b_head;
                ssize[b_head]+=ssize[a_head];
            }
            //arr[b_head] = a_head;
        }
    }
};

例题实战

547. 省份数量
这应该算是模板题~~

class dsu{
public:
    int arr[201];
    dsu(){
        for(int i = 0; i<201; ++i){
            arr[i] = i;
        }
    }
    void merge(int a, int b){ //将b并进a
        int a_head = find(a);
        int b_head = find(b);
        arr[b_head] = a_head;
    }
    int find(int i){
        if(i==arr[i]){
            return i;
        }
        return arr[i] = find(arr[i]);
    }
};
class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
        dsu ddsu;
        for(int i = 0; i<n; ++i){
            for(int j = 0; j<n; ++j){
                if(isConnected[i][j]==1){
                    ddsu.merge(i, j);
                }
            }
        }
        int res = 0;
        for(int i = 0; i<n; ++i){
            if(ddsu.arr[i]==i){
                res++;
            }
        }
        return res;
    }
};

128. 最长连续序列
刷并查集一定要看一下这题~~
思路就是把i并入i+1
((但最後似乎直接sort比较快...)

class dsu{
public:
    unordered_map<int, int> arr;
    int find(int target){
        if(!arr.count(target)){
            return target;
        }
        if(arr[target]==target){
            return target;
        }
        arr[target] = find(arr[target]);
        return arr[target];
    }
    //把b并进a
    void merge(int a, int b){
        int a_head = find(arr[a]);
        int b_head = find(arr[b]);
        arr[b] = a_head;
        return;
    }
};
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        dsu ddsu;
        for(auto i:nums){
            ddsu.arr[i]=i+1; //将i并入i+1
        }
        int ans=0;
        for(auto i:nums){
            int y=ddsu.find(i+1);
            ans=max(ans,y-i);
        }
        return ans;
    }
};