40 lines concise and easy understand c++ solution, union find 1D


  • 0
    A
    class Solution {
    public:
        vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
            vector<int> parent(m * n + 1, 0);
            for(int i = 0; i < parent.size(); i++) parent[i] = i;
            vector<int> result;
            if(positions.size() == 0) return result;
            unordered_set<int> isIsland;
            vector<pair<int, int>> dir{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
            for(int i = 0; i < positions.size(); i++) {
                isIsland.insert(positions[i].first * n + positions[i].second);
                int res = i == 0 ? 1 : result.back() + 1;
                for(int j = 0; j < 4; j++) {
                    int x = positions[i].first + dir[j].first;
                    int y = positions[i].second + dir[j].second;
                    if(x >= 0 && y >= 0 && x < m && y < n && isIsland.count(x * n + y)) {
                        int roota = find(parent, n, positions[i].first, positions[i].second);
                        int rootb = find(parent, n, x, y);
                        if(roota != rootb) {
                            unionset(parent, roota, rootb);
                            res--;
                        }
                    }
                }
                result.push_back(res);
            }
            return result;
        }
        
        int find(vector<int>& parent, int n, int x, int y) {
            int i = x * n + y;
            while(parent[i] != i) {
                parent[i] = parent[parent[i]];
                i = parent[i];
            }
            return i;
        }
        
        void unionset(vector<int>& parent, int roota, int rootb) {
            parent[roota] = parent[rootb];
        }
    };
    

Log in to reply
 

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