C++ standard union find with path compression beat 84.66%

• For details of union find, please refer to https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf

``````class Solution {
public:
vector<int> id;

vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
vector<int> res;
int cnt = 0;

id = vector<int>(m * n, -1);
for (int i = 0; i < positions.size(); i++) {
int idx = positions[i].first * n + positions[i].second;
if (id[idx] != -1) continue;

id[idx] = idx;
cnt++;

int top = idx - n;
if (top >= 0 && id[top] != -1) {
unite(idx, top);
cnt--;
}

int bottom = idx + n;
if (bottom < m * n && id[bottom] != -1 && !find(idx, bottom)) {
unite(idx, bottom);
cnt--;
}

if (positions[i].second > 0) {
int left = idx - 1;
if (id[left] != -1 && !find(idx, left)) {
unite(idx, left);
cnt--;
}
}

if (positions[i].second < n - 1) {
int right = idx + 1;
if (id[right] != -1 && !find(idx, right)) {
unite(idx, right);
cnt--;
}
}

res.push_back(cnt);
}

return res;
}

int root(int i) {
while (i != id[i]) {
id[i] = id[id[i]]; // path compression
i = id[i];
}
return i;
}

bool find(int p, int q) {
return root(p) == root(q);
}

void unite(int p, int q) {
int i = root(p);
int j = root(q);
id[i] = j;
}
};
``````

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