並查集是一種樹狀的結構，可以用來表示兩個節點的連接、查詢兩個節點的連接~~
在刷題的時候有時候會使用到，就直接把並查集刻出來

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;
    }
};