# [recommend for beginners]clean C++ implementation with detailed explaination

• I really want to kill myself when I find I mistake the '=' to '=='

``````   ALL IN ALL, this problem is really easy if you are familiar with the DFS.
``````

here is my implementation

`````` class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int m=grid.size();
if(m==0)  return 0;

int n=grid[0].size();
int result=0;
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(grid[i][j]=='1'){
help(i, j, grid);
result++;
}
}
}
return result;
}

void help(int i, int j, vector<vector<char>>& grid){
if(i<0 || i>=grid.size() || j<0 || j>=grid[0].size() || grid[i][j]=='0')   return;

grid[i][j]=='0';
help(i+1, j, grid);
help(i-1, j, grid);
help(i, j+1, grid);
help(i, j-1, grid);
return;
}
};``````

• ``````class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int m=grid.size();
if(m==0)    return 0;
int n=grid[0].size();

int result=0;
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(grid[i][j]=='1'){
help(i, j, grid);
result++;
}
}
}
return result;
}

void help(int i, int j, vector<vector<char>>& grid){
/*** make sure the corner condition is OK ***/
if(i<0 || i>=grid.size() || j<0 || j>=grid[0].size() || grid[i][j]=='0')
return;
grid[i][j]='0';
help(i+1, j, grid);
help(i-1, j, grid);
help(i, j+1, grid);
help(i, j-1, grid);
}
};``````

• Where is the `detailed explanation`?

• Update :　Number of Islands 2

Here is a post from the @dietpepsi

We use the UnionFind typical class defination to help us accelerate the code !

Here are the key points :

``````  change the 2D index to 1D representation

use the union find
``````

Here is AC implementation :

``````public class Solution {

private int[][] dir = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};

public List<Integer> numIslands2(int m, int n, int[][] positions) {
UnionFind2D islands = new UnionFind2D(m, n);
List<Integer> ans = new ArrayList<>();
for (int[] position : positions) {
int x = position[0], y = position[1];
int p = islands.add(x, y);
for (int[] d : dir) {
int q = islands.getID(x + d[0], y + d[1]);
if (q > 0 && !islands.find(p, q))
islands.unite(p, q);
}
}
return ans;
}
}
``````

}

Here is the defination of the Union Find class :

``````class UnionFind2D {
private int[] id;
private int[] sz;
private int m, n, count;

public UnionFind2D(int m, int n) {
this.count = 0;
this.n = n;
this.m = m;
this.id = new int[m * n + 1];
this.sz = new int[m * n + 1];
}

public int index(int x, int y) { return x * n + y + 1; }

public int size() { return this.count; }

public int getID(int x, int y) {
if (0 <= x && x < m && 0<= y && y < n)
return id[index(x, y)];
return 0;
}

public int add(int x, int y) {
int i = index(x, y);
id[i] = i; sz[i] = 1;
++count;
return i;
}

public boolean find(int p, int q) {
return root(p) == root(q);
}

public void unite(int p, int q) {
int i = root(p), j = root(q);
if (sz[i] < sz[j]) { //weighted quick union
id[i] = j; sz[j] += sz[i];
} else {
id[j] = i; sz[i] += sz[j];
}
--count;
}

private int root(int i) {
for (;i != id[i]; i = id[i])
id[i] = id[id[i]]; //path compression
return i;
}
}``````

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