# C++ _ 13ms

• I think the most important thoughts is:
https://en.wikipedia.org/wiki/Disjoint-set_data_structure

``````class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
if(grid.empty()) return 0;
int m = grid.size(), n = grid[0].size();
vector<vector<bool>> check(m,vector<bool>(n,false));
int island = 0;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(!check[i][j] && grid[i][j] == '1')
{
island++;
check[i][j] = true;
find(grid, check, i, j, m, n);
}
}
}
return island;
}

void find(vector<vector<char>>& grid, vector<vector<bool>>& check, int i, int j, int m, int n){
if(i - 1 >= 0 && !check[i-1][j] && grid[i-1][j] == '1'){
check[i-1][j] = true;
find(grid, check, i-1, j, m, n);
}
if(j - 1 >= 0 && !check[i][j-1] && grid[i][j-1] == '1'){
check[i][j-1] = true;
find(grid, check, i, j-1, m, n);
}
if(i + 1 < m && !check[i+1][j] && grid[i+1][j] == '1'){
check[i+1][j] = true;
find(grid, check, i+1, j, m, n);
}
if(j + 1 < n && !check[i][j+1] && grid[i][j+1] == '1'){
check[i][j+1] = true;
find(grid, check, i, j+1, m, n);
}
return;
}
};``````

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