# Union-find with path compression C++

• ``````class Solution {
private:
vector<pair<int,int>> direct = {{-1,0},{1,0},{0,1},{0,-1}};
vector<int> id;
vector<int> size;
public:
vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
vector<int> res;
int count = 0;
if(m == 0 || n == 0 || positions.size() == 0) {
res.push_back(count);
return res;
}
id = vector<int>(m * n, -1);
size = vector<int>(m * n, 0);
for(int i = 0; i < positions.size(); i++) {
int cur = positions[i].first * n + positions[i].second;
id[cur] = cur;
size[cur] = 1;
count++;
for(int j = 0; j < direct.size(); j++) {
int row = positions[i].first + direct[j].first;
int col = positions[i].second + direct[j].second;
int temp = row * n + col;
if(row >= 0 && row < m && col >= 0 && col < n && id[temp] != -1) {
if(find(cur) != find(temp)) {
count--;
unionSet(cur,temp);
}
}
}
res.push_back(count);
}
return res;
}

int find(int p) {
while(p != id[p]) {
id[p] = id[id[p]];
p = id[p];
}
return p;
}
void unionSet(int cur, int temp) {
int i = find(cur);
int j = find(temp);
if(i == j) return;
if(size[i] > size[j]) {
id[j] = i;
size[i] += size[j];
} else {
id[i] = j;
size[j] += size[i];
}
}
};``````

• I tried your solution but it got TLE at a case with 1 10000 and long positions. This solution has the same idea as the Java one. Why C++ version failed?

• I have just relaxed the constraint. The C++ version should now be accepted. Sorry about that.

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