547. Friend Circles

[namespace-io]

dfs

class Solution {
    
private:
    
    void dfs(int i, vector<vector<int>>& M, vector<int>& visit){
        visit[i] = true;
        
        for(int j = 0; j < M.size(); j++){
            if(!visit[j] && M[i][j] == 1){
                dfs(j, M, visit);
            }
        }
    }
public:
    int findCircleNum(vector<vector<int>>& M) {
        int n = M.size();
        vector<int> visit(n, false);
        int ans  = 0;
        for(int i = 0; i < n; i++){
            if(!visit[i]) {
                dfs(i, M, visit);
                ans++;
            }
        }
        
        return ans;
    }
};

采用路径压缩和按秩合并

class Solution {
private:
    vector<int> Rank;
    vector<int> v;

     void Union(int i, int j){
        int ri = Find(i);
        int rj = Find(j);
        if(ri == rj) return ;

        if(Rank[ri] > Rank[rj]){
            v[rj] = ri;
        } else if(Rank[ri] < Rank[rj]){
            v[ri] = rj;
        } else {
            Rank[ri] += 1;
            v[rj] = ri;
        }
    }
    
    int Find(int i){
        if(v[i] != i) v[i] = Find(v[i]);
        return v[i];
    }
    
public:
    int findCircleNum(vector<vector<int>>& M) {
        int n = M.size();
        for(int i = 0; i < n; i++){
            v.push_back(i);
            Rank.push_back(0);
        }
        
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                if(M[i][j] == 1){
                    Union(i, j);
                }
            }
        }
        
        
        int cnt = 0;
        
        for(int i = 0; i < n; i++){
            if(Find(i) == i) cnt++;
        }
        
        return cnt;
    }
};

并查集 还未优化

class Solution {
    
    vector<int> v;
    void Union(int i, int j){
        int pi = Find(i);
        int pj = Find(j);
        
        v[pi] = pj;
    }
    
    int Find(int i){
        
        while(v[i] != i) i = v[i];
        
        return i;
    }
public:
    int findCircleNum(vector<vector<int>>& M) {
        int n = M.size();
        for(int i = 0; i < n; i++){
            v.push_back(i);
        }
        
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                if(M[i][j] == 1){
                    Union(i, j);
                }
            }
        }
        
        
        set<int> s;
        
        for(int i = 0; i < n; i++){
            s.insert(Find(i));
        }
        
        return s.size();
    }
};