# C++ solution with Union find class

• class Union{

public:

``````vector<int>parent;
vector<int>size;
int cou ;
Union(int n){
parent =vector<int>(n);
size = vector<int>(n,1);
for(int i =0;i< n;i++)
parent[i] = i;
cou = n;
}

int count(){
return cou;
}

void connect(int a,int b){
int aa = find(a);
int bb = find(b);
if(aa ==bb)
return ;

if(size[aa] <= size[bb]){
size[bb] +=size[aa];
parent[aa] = bb;

}else{
size[aa] +=size[bb];
parent[bb] = aa;
}

cou --;
}

bool isConnect(int a,int b){
return find(a) == find (b);
}

int find(int m){
if(parent[m] == m)
return m;

parent[m] = find(parent[m]);

return parent[m];
}
``````

};

class Solution {
public:

``````int numIslands(vector<vector<char>>& grid) {
int m = grid.size();
if(m==0)
return 0;
int n = grid[0].size();
Union u = Union(m*n);
int first = false;
int is = 0;
for(int i =0;i<m;i++){
for(int j =0;j<n ;j++){
int tmp = n*i +j;
if(grid[i][j] == '1'){
if(i+1 < m && grid[i+1][j] == '1')
u.connect(tmp,(i+1)*n+j);
if(i-1 >=0 && grid[i-1][j] == '1')
u.connect(tmp,(i-1)*n+j);
if(j+1 < n && grid[i][j+1] == '1')
u.connect(tmp,(i)*n+j+1);
if(j-1 >=0 && grid[i][j-1] == '1')
u.connect(tmp,(i)*n+j-1);
}else{
if(first == false){
is = i *n +j;
first =true;
}else{
u.connect(is,i*n+j);
}
}
}
}

return u.count() - first;
}
``````

};

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