# Union-find with path compression C++ solution, 148 ms, beats 100%

• ``````class Solution {
public:
vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
vector<int> result;
vector<int> init(n*m, -1);
nodes_.swap(init);
const vector<pair<int, int>> extends = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int count = 0;
for(auto p:positions){
const int ind = p.first * n + p.second;
if(nodes_[ind]<0){
++count;
nodes_[ind] = ind;
for(auto& e:extends){
const int x = p.first+e.first;
const int y = p.second+e.second;
const int new_ind = x*n + y;
if(x>=0 && x<m && y>=0 && y<n && nodes_[new_ind]>=0){
const int root = find(ind);
const int new_root = find(new_ind);
if(root != new_root){
--count;
unite(root, new_root);
}
}
}
}
result.push_back(count);
}
return result;
}
private:
void unite(int p, int q){
if(p!=q){
nodes_[q] = p;
}
}

//find root
int find(int id){
int org = id;
while(id!=nodes_[id]){
id = nodes_[nodes_[id]];
}
int t = 0;
for(int i=org; i!=nodes_[i]; i=t){
t= nodes_[i];
nodes_[i] = id;
}
return id;
}

private:
vector<int> nodes_;
};``````

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