WeightedUnion2DFind algorithm

class WeightedUnion2DFind
{
public:
    WeightedUnion2DFind(int m, int n,int cnt)
    {
        for(int i = 0;i        for(int i = 0;i        count = cnt;
        M = m;
        N = n;
    }
    int size(){return count++;}
   
    // find root id for current node
    int find(int p)
    {
         while(p!=ids[p]) p= ids[p];
         return p;
    }
    bool connected(int p,int q)
    {
        return find(p) == find(q);
    }
    void Union(int p, int q) //replace the sets containing two items by their union.
    {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ)
            return;
       
        if (szs[rootP] < szs[rootQ]) ids[rootP] = rootQ;
        else if (szs[rootP] == szs[rootQ]) {
            ids[rootQ] = rootP;
            szs[rootP] += 1;
        }
        else
            ids[rootQ] = rootP;
        count--;
    }
private:
      vector ids; // id[i] = parent of i
      vector szs; // sz[i] = number of objects in subtree rooted at i
      int M,N,count;
};

class Solution {
public:
    int numIslands(vector>& grid) {
        int m = grid.size();
        if(m == 0) return 0;
        int n = grid[0].size();
        int count = 0;
        for(int i = 0;i            for(int j = 0;j                if(grid[i][j]=='1') count++;
        WeightedUnion2DFind UF(m,n,count);
        vector> visited(m,vector(n));
        int direction[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
        for(int i = 0;i            for(int j = 0;j            {
                if(grid[i][j]=='1')
                {
                   
                    //check all neigboring pixels.
                    for(int k = 0;k<4 br="" k="">                    {
                        int dx = i+direction[k][0];
                        int dy = j+direction[k][1];
                        if(!(dx>=0 && dx=0 && dy                        if( grid[dx][dy]=='1')
                            UF.Union(i*n+j,dx*n+dy);
                    }
                }
            }
        return UF.size();
    }   
};