# C++ Union Find Set Solution

• ``````class Solution {
public:
vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
vector<int> ret;
vector<vector<int>> hash(m + 5, vector<int>(n + 5, -1));
father.clear();
int tx[4] = {0, 0, 1, -1},
ty[4] = {1, -1, 0, 0};
int ans = 0;
for (int i = 0; i < positions.size(); ++ i){
int x = positions[i].first, y = positions[i].second;
hash[x][y] = i;
father.push_back(i);
ans ++;
for (int k = 0; k < 4; ++ k){
if (x + tx[k] >= 0 && y + ty[k] >= 0 && x + tx[k] < m && y + ty[k] < n && hash[x + tx[k]][y + ty[k]] != -1){
if (getfather(hash[x + tx[k]][y + ty[k]]) != getfather(hash[x][y])){
father[getfather(hash[x][y])] = getfather(hash[x + tx[k]][y + ty[k]]);
ans --;
}
}
}
ret.push_back(ans);
}
return ret;
}
private:
vector<int> father;
int getfather(int c){
if (father[c] != c) father[c] = getfather(father[c]);
return father[c];
}
};``````

• why m+5 and n+5?

``vector<vector<int>> hash(m + 5, vector<int>(n + 5, -1));``

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