union find AC solution


  • 2
    I
    class Solution {
    public:
        int findParent(unordered_map<int,int> &m, int pt){
            int parent = pt;
            while(parent != m[parent])
                parent = m[parent];
            int p = pt;
            while(m[p] != parent)
            {
                int tmp = m[p];
                m[p] = parent;
                p = tmp;
            }
            return parent;
        }
        void unite(unordered_map<int,int> &m, int a, int b, int &res){
            int pa = findParent(m,a);
            int pb = findParent(m,b);
            if(pa != pb)
            {
                m[pa] = pb;
                --res;
            }
        }
        int findCircleNum(vector<vector<int>>& M) {
            int n = M.size();
            if(!n) return 0;
            unordered_map<int,int> m;
            for(int i = 0; i < n; ++i)
               m[i] = i;
            int res = n;
            for(int i = 0; i < n; ++i)
            for(int j = i+1; j < n; ++j)
            {
                if(M[i][j] == 1)
                {
                    unite(m,i,j,res);
                }
            }
            return res;
        }
    };
    

Log in to reply
 

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