# Using weighted quick-union and path compression O(klogmn)

• Please read this document first. After the reading you would have full understanding of union find algorithm
https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf

``````class Solution {
public:
vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
vector<int> roots(m*n,-1);
vector<int> sz(m*n,1);
vector<vector<int>> dir = {{0,1},{0,-1},{1,0},{-1,0}};
vector<int> res;
int cnt = 0;
for(int i=0;i<positions.size();i++){
int id1 = positions[i].first*n + positions[i].second;
roots[id1] = id1;
cnt++;
for(int j=0;j<dir.size();j++){
int y = positions[i].first  + dir[j][0];
int x = positions[i].second + dir[j][1];
int id2 = y*n+x;
if(x>=0 && x<n && y>=0 && y<m && roots[id2] !=-1){
unite(roots,sz,findRoot(roots, id2),findRoot(roots, id1),cnt);
}
}
res.push_back(cnt);
}
return res;
}
int findRoot(vector<int> & roots, int id){
while(roots[id]!= id){
//pass compression
roots[id] = roots[roots[id]];
id = roots[id];
}
return id;
}
void unite(vector<int> &roots, vector<int> &sz, int root1, int root2,int &cnt){
if(root1!=root2) cnt--;
//weighted quick_union
if(sz[root1]<sz[root2]){
sz[root2]+=sz[root1];
roots[root1] = root2;
}else{
sz[root1]+=sz[root2];
roots[root2] = root1;
}
}
};
``````

• @primbo amazing link and implementation.

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