clean union find AC solution


  • 0
    B
    class Solution {
        int getf(vector<int> &f, int i){
            if(f[i]==i){
                return i;
            }
            int t=getf(f, f[i]);
            f[i]=t;
            return t;
        }
    public:
        int findCircleNum(vector<vector<int>>& M) {
            int n=M.size();
            vector<int> f(n);
            for(int i=0;i<n;++i){
                f[i]=i;
            }
            int re=n;
            for(int i=0;i<n;++i){
                for(int j=i+1;j<n;++j){
                    if(M[i][j]==1){
                        int fi=getf(f, i);
                        int fj=getf(f, j);
                        if(fi!=fj){
                            f[fi]=fj;
                            --re;
                        }
                    }
                }
            }
            return re;
        }
    };
    

Log in to reply
 

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