C++ union find

• ``````struct DJSetNode {
int label;
int rank;
DJSetNode* parent;
DJSetNode(int lb,int r,DJSetNode* p):label(lb),rank(r),parent(p) {}
};

class Solution {
unordered_set<DJSetNode*> forest;

DJSetNode* makeNode() {
DJSetNode* cur = new DJSetNode(0,0,nullptr);
forest.insert(cur);
return cur;
}

DJSetNode* find(DJSetNode* n) {
if(n==nullptr) return n;
while(n->parent) {
n = n->parent;
}
return n;
}

DJSetNode* merge(DJSetNode* n1, DJSetNode* n2) {
DJSetNode* r1 = find(n1);
DJSetNode* r2 = find(n2);
if(r1==r2)  return r1; // same tree
else if(r1->rank > r2->rank) {
r2->parent = r1;
forest.erase(r2);
return r1;
} else if(r1->rank < r2->rank) {
r1->parent = r2;
forest.erase(r1);
return r2;
} else {
r2->parent = r1;
forest.erase(r2);
r1->rank++;
return r1;
}
}

vector<DJSetNode*> nbs;
int x = p.first;
int y = p.second;
DJSetNode* cur = makeNode();
Map[x][y] = cur;
if(x>0 && Map[x-1][y]) cur = merge(cur,Map[x-1][y]);
if(y>0 && Map[x][y-1]) cur = merge(cur,Map[x][y-1]);
if(x<M-1 && Map[x+1][y]) cur = merge(cur,Map[x+1][y]);
if(y<N-1 && Map[x][y+1]) cur = merge(cur,Map[x][y+1]);
return forest.size();
}
int M,N;
vector<vector<DJSetNode*>> Map;
public:
vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
M = m;
N = n;
Map = vector<vector<DJSetNode*>>(m,vector<DJSetNode*>(n,nullptr));
vector<int> ans;
for(auto p : positions) {