Union Find by adding labels and changing labels(naive but not slow)


  • 0
    Y
    class Solution {
    private: 
        vector<vector<int>> Labels;
        unordered_map<int, vector<pair<int,int>>> Islands;
        int num_islands;
        int max_label;
    
    public:
        
        vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
            Labels= vector<vector<int>> (m, vector<int> (n,0));
            num_islands=0;
            max_label=0;
            vector<int> result;
            for (auto P: positions){
                AddLand(P.first, P.second, m, n);
                result.push_back(num_islands);
            }
            return result;
        }
        
        void AddLand (int x, int y, int m, int n) {
            set<int> adjacent_islands;
            int A[5]={0,1,0,-1,0};
            for (int i=0; i<4; i++){
                if (x+A[i]>=0 && x+A[i]<m && y+A[i+1]>=0 && y+A[i+1]<n) {
                    if (Labels[x+A[i]][y+A[i+1]]!=0) adjacent_islands.insert(Labels[x+A[i]][y+A[i+1]]);
                }
            }
            num_islands+=1-adjacent_islands.size();
            if (adjacent_islands.size()==0){
                max_label++;
                Labels[x][y]=max_label;
                Islands[max_label].push_back(make_pair(x,y));
            }
            else {
                int K=*adjacent_islands.begin();
                Labels[x][y]=K;
                Islands[K].push_back(make_pair(x,y));
                for (int k: adjacent_islands){
                    if (k!=K) {
                        for (auto p: Islands[k]){
                            Labels[p.first][p.second]=K;
                            Islands[K].push_back(p);
                        }
                        Islands[k].clear();
                    }
                }
            }
        }
    };

Log in to reply
 

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