Clean C++ Union Find


  • 0
    class Solution {
    public:
        vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
            vector<int>res;
            vector<vector<int>>matrix(m, vector<int>(n));
            int tag = 0, count = 0;
            for(auto x: positions) addLand(matrix, m, n, x.first, x.second, tag, count, res);
            return res;
        }
        
        void addLand(vector<vector<int>>& matrix, int m, int n, int r, int c, int& tag, int& count, vector<int>& res){
            unordered_set<int>s;
            vector<int>dir(4);
            if(c - 1 >= 0) dir[0] = matrix[r][c - 1];
            if(c + 1 < n)  dir[1] = matrix[r][c + 1];
            if(r - 1 >= 0) dir[2] = matrix[r - 1][c];
            if(r + 1 < m)  dir[3] = matrix[r + 1][c];
            for(auto x: dir) if(x) s.insert(x);
            matrix[r][c] = s.empty() ? ++tag : *s.begin();
            count -= s.size() - 1;
            res.push_back(count);
            if(s.size() > 1){
                BFS(matrix, m, n, r, c - 1, *s.begin());
                BFS(matrix, m, n, r, c + 1, *s.begin());
                BFS(matrix, m, n, r - 1, c, *s.begin());
                BFS(matrix, m, n, r + 1, c, *s.begin());
            }
        }
        
        void BFS(vector<vector<int>>& matrix, int m, int n, int r, int c, int tag){
            if(r < 0 || c < 0 || r == m || c == n || matrix[r][c] == 0 || matrix[r][c] == tag) return;
            matrix[r][c] = tag;
            BFS(matrix, m, n, r, c - 1, tag);
            BFS(matrix, m, n, r, c + 1, tag);
            BFS(matrix, m, n, r - 1, c, tag);
            BFS(matrix, m, n, r + 1, c, tag);
        }
    };
    

Log in to reply
 

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