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


  • 1
    A

    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;
        }
    };
    

Log in to reply
 

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