Easy Understanding C++ Code


  • 0
    M
    class Solution {
    private:
        int ufs_find(vector<int>& nodes, int x) {
            if(nodes[x]<0) return x;
            return nodes[x] = ufs_find(nodes, nodes[x]);
        }
        
        void ufs_union(vector<int>& nodes, int x, int y) {
            int rx = ufs_find(nodes, x);
            int ry = ufs_find(nodes, y);
            if(rx!=ry) {
                nodes[rx] += nodes[ry];
                nodes[ry] = rx;
            }
        }
    
    public:
        int findCircleNum(vector<vector<int>>& M) {
            int N = M.size();
            vector<int> nodes(N, -1);
            
            for(int i=0;i<N;++i) {
                for(int j=i+1;j<N;++j) {
                    if(M[i][j]) ufs_union(nodes, i, j);
                }
            }
            
            int ans=0;
            for(int i=0;i<N;++i) {
                if(nodes[i]<0) ++ans;
            }
            return ans;
        }
    };
    

Log in to reply
 

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