# C++ Solution using Union Find data structure with path compression

• ``````class Solution {
public:
vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
vector<int> ans;
if(!m || !positions.size()){
ans.push_back(0);
return ans;
}

vector<int> fa(m*n);
vector<bool> isisland(m*n);
for(int i = 0; i < m*n; ++ i){
fa[i] = -1;
isisland[i] = false;
}
int cnt = 0;
ans.resize(positions.size());
for(int i = 0; i < positions.size(); ++ i){
int cur = positions[i].first*n + positions[i].second;
//       printf("%d -> ", cur);
++ cnt;
isisland[cur] = true;
if(!i){
ans[i] = cnt;
}else{
for(int j = 0; j < 4; ++ j){
int nxt = 0, nxtx = positions[i].first + dir[j][0], nxty = positions[i].second + dir[j][1];
nxt = nxtx*n + nxty;
if(nxtx >= 0 && nxtx < m && nxty >= 0 && nxty < n && isisland[nxt] && nxt != cur){
//     printf("x = %d, y = %d, nxt = %d;;; ",nxtx, nxty, nxt);
if(find(nxt, fa) != find(cur, fa)){
unionset(cur, nxt, fa);
-- cnt;
}
}
}
ans[i] = cnt;
}
//   puts("");
}
return ans;
}
private:
int find(int u, vector<int> &fa){
int s = u;
for(; fa[s] >= 0; s = fa[s]) ;
while(u != s){
int tmp = fa[u];
fa[u] = s;
u = tmp;
}
return s;
}

void unionset(int u, int v, vector<int> &fa){
int fa1 = find(u, fa), fa2 = find(v, fa);
int tmp = fa[fa1]+fa[fa2];
if(fa[fa1] > fa[fa2]){
fa[fa1] = fa2;
fa[fa2] = tmp;
}else{
fa[fa1] = tmp;
fa[fa2] = fa1;
}
}
private:
int dir[4][2]={{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
};``````

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