# Accepted C++ union find solution

``````class Solution {
public:
int total;
int find(vector<int> & parents, int index) {
if(parents[index]==-1)return index;
return find(parents, parents[index]);
}
void merge(vector<int> & parents, int a, int b){
int parent_a = find(parents, a);
int parent_b = find(parents, b);
if(parent_a!=parent_b){
parents[parent_b]=parent_a;//set the new 's parent to be old one.
total--;
}
}
int numIslands(vector<vector<char>>& grid) {
int rows = grid.size();
if (rows==0) return 0;
int cols = grid[0].size();
vector<int>parents(rows*cols,-1);//use array at first all initialized as -1;
for(int i=0;i<rows;i++){
for(int j=0;j<cols;j++){
if(grid[i][j]=='0') total--;
//now all 1s
else{
int index = i*cols+j;
//we only need to consider those we have visited and merge with them, so only two neighbers are considered.
//the neigher needs to be '1'.
if(i>0 && grid[i-1][j]=='1'){
merge(parents, (i-1)*cols+j, index);
}
if(j>0 && grid[i][j-1]=='1'){
merge(parents, i*cols+j-1, index);
}
}
}
}