前言

早上好，
最近蠻喜歡寫union find的題目，感覺大致都一樣，但會有些變化

題目連結

解題

大致跟上一篇一樣（Find_ function跟merge 一模一樣），只是改了一些 main(findCircleNum)裡的東西

具體更改

1. 如果與自己連結的點已經出現父節點，那就把這個點加入(連結)至該父節點，否則就指定自己為父節點
2. 如果自己(該點)已經有連結，加入連結的點，否則指定自己為父節點
3. 查找每個點連結的父節點，查看有幾個父節點

code連結

class Solution {
public:
    int Find_(vector<int> &f,int x){
        if(f[x] != x){
            f[x] = Find_(f,f[x]);
        }
        return f[x];
    }
    void merge(vector<int> &f,vector<int> &rank,int x,int y){
        x = Find_(f,x);
        y = Find_(f,y);

        if(x==y) return;

        if(x < y){
            swap(x,y);
        }

        f[y] = x;
        rank[x] += rank[y];
    }
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
        vector<int> f(n),rank(n);

        for(int i = 0;i < n;i++){
            f[i] = i;
            rank[i] = 1;
        }
        
        map<int,int> have;

        for(int i = 0;i < n;i++){
            for(int j = 0;j < n;j++){
                if(i != j && isConnected[i][j] == 1){
                    // if have j root
                    if(have.count(j)){
                        merge(f,rank,i,have[j]);
                    }
                    else{
                        have[j] = i;
                    }
                }
            }
            if(have.count(i)){
                merge(f,rank,i,have[i]);
            }
            else{
                have[i] = i;
            }
        }
        set<int> ans;
        //find root
        for(int i = 0;i < n;i++){
            ans.insert(Find_(f,i));
        }
        return ans.size();
    }
};