# c++ union find solution

• ``````class Solution {
public:
vector<int> parent;
vector<int> size;
void init(vector<int> &parent, vector<int> &size, int m, int n) {
for(int i = 0; i < m; i ++) {
for(int j = 0; j < n; j ++) {
parent.push_back(i*n + j);
size.push_back(1);
}
}
}
int findParent(int a) {
if(parent[a] == a) return a;
parent[a] = findParent(parent[a]);
return parent[a];
}
void linkBySize(int a, int b) {
int pa = findParent(a);
int pb = findParent(b);
if(pa == pb) return;
if(size[pa] >= size[pb]) {
size[pa] += size[pb];
parent[pb] = pa;
}
else {
size[pb] += size[pa];
parent[pa] = pb;
}
}
int numIslands(vector<vector<char>>& grid) {
int m = grid.size();
if(!m) return 0;
int n = grid[0].size();
init(parent, size, m, n);
for(int i = 0; i < m; i ++) {
for(int j = 0; j < n; j ++) {
if(grid[i][j] == '1') {
int i_down = min(i+1, m-1);
int j_right = min(j+1, n-1);
if(grid[i][j_right] == '1') linkBySize(i*n + j, i*n + j_right);
if(grid[i_down][j] == '1') linkBySize(i*n + j, i_down*n + j);
}
}
}
int cnt = 0;
for(int i = 0; i < m; i ++) {
for(int j = 0; j < n; j ++) {
if(grid[i][j] == '1' && parent[i*n+j] == i*n+j) {
cnt ++;
}
}
}
return cnt;
}
};
``````

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