C++ Union Find Set Solution


  • 0
    N
    class Solution {
    public:
        vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
            vector<int> ret;
            vector<vector<int>> hash(m + 5, vector<int>(n + 5, -1));
            father.clear();
            int tx[4] = {0, 0, 1, -1},
                ty[4] = {1, -1, 0, 0};
            int ans = 0;
            for (int i = 0; i < positions.size(); ++ i){
                int x = positions[i].first, y = positions[i].second;
                hash[x][y] = i;
                father.push_back(i);
                ans ++;
                for (int k = 0; k < 4; ++ k){
                    if (x + tx[k] >= 0 && y + ty[k] >= 0 && x + tx[k] < m && y + ty[k] < n && hash[x + tx[k]][y + ty[k]] != -1){
                        if (getfather(hash[x + tx[k]][y + ty[k]]) != getfather(hash[x][y])){
                            father[getfather(hash[x][y])] = getfather(hash[x + tx[k]][y + ty[k]]);
                            ans --;
                        }
                    }
                }
                ret.push_back(ans);
            }
            return ret;
        }
    private:
        vector<int> father;
        int getfather(int c){
            if (father[c] != c) father[c] = getfather(father[c]);
            return father[c];
        }
    };

  • 0
    Z

    why m+5 and n+5?

    vector<vector<int>> hash(m + 5, vector<int>(n + 5, -1));

Log in to reply
 

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