Union-find with path compression C++


  • 0
    S
    class Solution {
    private:
        vector<pair<int,int>> direct = {{-1,0},{1,0},{0,1},{0,-1}};
        vector<int> id;
        vector<int> size;
    public:
        vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
            vector<int> res;
            int count = 0;
            if(m == 0 || n == 0 || positions.size() == 0) {
                res.push_back(count);
                return res;
            }
            id = vector<int>(m * n, -1);
            size = vector<int>(m * n, 0);
            for(int i = 0; i < positions.size(); i++) {
                int cur = positions[i].first * n + positions[i].second;
                id[cur] = cur;
                size[cur] = 1;
                count++;
                for(int j = 0; j < direct.size(); j++) {
                    int row = positions[i].first + direct[j].first;
                    int col = positions[i].second + direct[j].second;
                    int temp = row * n + col;
                    if(row >= 0 && row < m && col >= 0 && col < n && id[temp] != -1) {
                        if(find(cur) != find(temp)) {
                            count--;
                            unionSet(cur,temp);
                        }
                    }
                }
                res.push_back(count);
            }
            return res;
        }
        
        int find(int p) {
            while(p != id[p]) {
                id[p] = id[id[p]];
                p = id[p];
            }
            return p;
        }
        void unionSet(int cur, int temp) {
            int i = find(cur);
            int j = find(temp);
            if(i == j) return;
            if(size[i] > size[j]) {
                id[j] = i;
                size[i] += size[j];
            } else {
                id[i] = j;
                size[j] += size[i];
            }
        }
    };

  • 0
    A

    I tried your solution but it got TLE at a case with 1 10000 and long positions. This solution has the same idea as the Java one. Why C++ version failed?


  • 0

    I have just relaxed the constraint. The C++ version should now be accepted. Sorry about that.


Log in to reply
 

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