C++ union-find solution with Path Compression


  • 12
    L

    This is a C++ implementation based @yavinci 's solution, which implemented using Java. For more detailed Explanations, please see https://leetcode.com/discuss/69572/easiest-java-solution-with-explanations

    vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
        vector<int> res;
        roots = vector<int>(m * n, -1);
        vector<pair<int, int>> dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        int island = 0;
        for (auto pos : positions) {
            int x = pos.first, y = pos.second, idx_p = x * n + y;
            roots[idx_p] = idx_p;
            ++island;
            for (auto dir : dirs) {
                int row = x + dir.first, col = y + dir.second, idx_new = row * n + col;
                if (row >= 0 && row < m && col >= 0 && col < n && roots[idx_new] != -1) {
                    int rootNew = findRoot(idx_new), rootPos = findRoot(idx_p);
                    if (rootPos != rootNew) {
                        roots[rootPos] = rootNew;
                        --island;
                    }
                }
            }
            res.push_back(island);
        }
        return res;
    }
    
    private:
    vector<int> roots;
    int findRoot(int idx) {
        while(idx != roots[idx]) {
            roots[idx] = roots[roots[idx]]; 
            idx = roots[idx];
        }
        return idx;
    }
    

  • 0
    T

    roots = vector<int>(m * n, -1); the time complexity is O(m*n)


  • 0
    G

    @touzi Not true. The algorithm does not visit every index.


  • 2
    Q

    @gaihao But initializing the vector with -1 takes O(m*n), right?


Log in to reply
 

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