# Share my cpp unionfind solution with path compression

• ``````class UnionFind {
public:
UnionFind(int n) {
nodes.reserve(n);
for(int i = 0; i < n; i++)
nodes.push_back(node(i));
count = n;
}

void unionSets(int idx1, int idx2) {
int parent1 = findSet(idx1);
int parent2 = findSet(idx2);
if(parent1 == parent2)
return;
nodes[parent2].parent = &nodes[parent1];
count--;
}

int findSet(int idx) {
struct node* cur = &nodes[idx];
while(cur -> parent)
cur = cur -> parent;
struct node* root = cur;
cur = &nodes[idx];
while(cur != root) {
struct node* next = cur -> parent;
cur -> parent = root;
cur = next;
}
return root -> num;
}

int countOfSets() {
return count;
}

private:
struct node {
int num;
node* parent;
node(int n) : num(n), parent(NULL) {}
};

vector<node> nodes;
int count;
};

class Solution {
public:
vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
vector<int> res;
vector<vector<bool> > map(m, vector<bool>(n, false));
int totalArea = m * n;
int landArea = 0;
UnionFind unionFind(m * n);
auto getIdx = [n](int i, int j) {return n * i + j;};
for(pair<int, int> pos : positions) {
int i = pos.first, j = pos.second;
if(map[i][j])
continue;
map[i][j] = true;
landArea++;
if(i > 0 && map[i - 1][j])
unionFind.unionSets(getIdx(i, j), getIdx(i - 1, j));
if(j > 0 && map[i][j - 1])
unionFind.unionSets(getIdx(i, j), getIdx(i, j - 1));
if(i  < m - 1 && map[i + 1][j])
unionFind.unionSets(getIdx(i, j), getIdx(i + 1, j));
if(j < n - 1 && map[i][j + 1])
unionFind.unionSets(getIdx(i, j), getIdx(i, j + 1));
res.push_back(unionFind.countOfSets() - totalArea + landArea);
}
return res;
}

};``````

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