# Untitled

unknown
c_cpp
7 months ago
1.5 kB
3
Indexable
Never
```class Solution {
public:
unordered_map<int, int>parent;
int find(int a){
return parent[a] == a?a:parent[a] = find(parent[a]);
}
int combine(int a, int b){
int pa = find(a), pb = find(b);
if(pa == pb)
return 0;
parent[pa] = pb;
return 1;
}
vector<int> numIslands2(int m, int n, vector<vector<int>>& positions) {
vector<int>ans;
int comp = 0;
int row_dir[2] = {1, -1};//Move in the same row
int col_dir[2] = {n, -n};//Move in the same column
for(auto p: positions){
int coord = p[0]*n+p[1];
ans.push_back(comp);
continue;
}
comp++;
parent[coord] = coord;
for(int i = 0; i < 2; i++){
int new_coord = coord+row_dir[i];
if(new_coord/n != coord/n)//Not in the same row
continue;             //Avoid the flaw of using single num
if(parent.count(new_coord))
comp -= combine(coord, new_coord);
}
for(int i = 0; i < 2; i++){
int new_coord = coord+col_dir[i];
if(parent.count(new_coord))
comp -= combine(coord, new_coord);
}
ans.push_back(comp);
}
return ans;
}
//Time O(m*n)
//Space O(m*n)
};```