C++ Non-recursive Union-Find solution, 6ms

• 47 / 47 test cases passed
Status: Accepted
Runtime: 6 ms

``````class Solution {
public:
unsigned long long fp(vector<vector<unsigned long long>>& v, uint r, uint c) {
unsigned long long p;
while ((p = (unsigned long long)r<<32 | c) != v[r][c]) {
uint rn = v[r][c] >> 32, cn = v[r][c];
v[r][c] = v[rn][cn], r = rn, c = cn;
}
return p;
}
bool un(vector<vector<unsigned long long>>& v, uint r, uint c, uint i, uint j) {
unsigned long long p1 = fp(v, r, c), p2 = fp(v, i, j);
if (p1 == p2) return false;
v[(uint)(p2>>32)][(uint)p2] = p1;
return true;
}
int numIslands(vector<vector<char>>& grid) {
uint n = 0, h = grid.size(), w = h ? grid[0].size() : 0;
vector<vector<unsigned long long>> v(h, vector<unsigned long long>(w));
for (uint i = 0; i < h; i++) {
for (uint c = 0, j = 0; j < w; j++, c = 0) {
if (grid[i][j] == '0') continue;
if ((!i || grid[i-1][j] == '0') && (!j || grid[i][j-1] == '0')) v[i][j] = (unsigned long long)i<<32 | j, n++;
else {
if (i && grid[i-1][j] == '1') v[i][j] = fp(v, i-1, j), c++;
if (j && grid[i][j-1] == '1') {
if (!c) v[i][j] = fp(v, i, j-1);
else if (un(v, i, j, i, j-1)) n--;
}
}
}
}
return n;
}
};
``````

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