[547. Friend Circles] C++ _ DFS and Union Find, two methods


  • 0

    DFS:

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

    Union Find:

    class Solution {
    public:
    int findCircleNum(vector<vector<int>>& M) {
        if(M.empty()) return 0;
        int n = M.size();
        int res = 0;
        if(n == 1) return 1;
        vector<int> vec(n);
        for(int i = 0; i < n; ++i){
            vec[i] = i;
        }
        for(int i = 0; i < n - 1; ++i){
            for(int j = i + 1; j < n; ++j){
                if(M[i][j]){
                    int k = i;
                    while(vec[k] != k) k = vec[k];
                    if(k < vec[j]) {vec[k] = vec[j];}
                    else{vec[j] = k;}
                }
            }
        }
        for(int i = 0; i < n; ++i){
            int k = i;
            while(vec[k] != k) k = vec[k];
            vec[i] = k;
        }
        unordered_set<int> st;
        for(auto v : vec){
            if(st.find(v) == st.end()) {res++; st.insert(v);}
        }
        return res;
    }
    };

Log in to reply
 

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