C++ Union Find


  • 0
    F
    int answer;
    vector<int> father;
    int find(int x){
        if(father[x] == x){
            return x;
        }
        return father[x] = find(father[x]);
    }
    
    void connect(int a, int b){
        int roota = find(a);
        int rootb = find(b);
        if(roota != rootb){
            father[roota] = rootb;
            answer--;
        }
    }
    int findCircleNum(vector<vector<int>>& M) {
        int n = M.size();
        answer = n;
        father.resize(n);
        for(int i = 0; i < n; i++){
            father[i] = i;
        }
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(M[i][j] == 1){
                    connect(j, i);
                }
            }
        }
        return answer;
    }
    void connect(int a, int b){
        int roota = find(a);
        int rootb = find(b);
        if(roota != rootb){
            father[roota] = rootb;
            answer--;
        }
    }
    int findCircleNum(vector<vector<int>>& M) {
        int n = M.size();
        answer = n;
        father.resize(n);
        for(int i = 0; i < n; i++){
            father[i] = i;
        }
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(M[i][j] == 1){
                    connect(j, i);
                }
            }
        }
        return answer;
    }

  • 0
    F

    @fangyan sorry! Ignore the last 2 functions. I mistakenly copy and paste that.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.