C++ Solution using Union Find data structure with path compression


  • 0
    Y
    class Solution {
    public:
        vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
            vector<int> ans;
            if(!m || !positions.size()){
                ans.push_back(0);
                return ans;
            }
            
            vector<int> fa(m*n);
            vector<bool> isisland(m*n);
            for(int i = 0; i < m*n; ++ i){
                fa[i] = -1;
                isisland[i] = false;
            }
            int cnt = 0;
            ans.resize(positions.size());
            for(int i = 0; i < positions.size(); ++ i){
                int cur = positions[i].first*n + positions[i].second;
         //       printf("%d -> ", cur);
                ++ cnt;
                isisland[cur] = true;
                if(!i){
                    ans[i] = cnt;
                }else{
                    for(int j = 0; j < 4; ++ j){
                        int nxt = 0, nxtx = positions[i].first + dir[j][0], nxty = positions[i].second + dir[j][1];
                        nxt = nxtx*n + nxty;
                        if(nxtx >= 0 && nxtx < m && nxty >= 0 && nxty < n && isisland[nxt] && nxt != cur){
                       //     printf("x = %d, y = %d, nxt = %d;;; ",nxtx, nxty, nxt);
                            if(find(nxt, fa) != find(cur, fa)){
                                unionset(cur, nxt, fa);
                                -- cnt;
                            }
                        }
                    }
                    ans[i] = cnt;
                }
             //   puts("");
            }
            return ans;
        }
    private:
        int find(int u, vector<int> &fa){
            int s = u;
            for(; fa[s] >= 0; s = fa[s]) ;
            while(u != s){
                int tmp = fa[u];
                fa[u] = s;
                u = tmp;
            }
            return s;
        }
        
        void unionset(int u, int v, vector<int> &fa){
            int fa1 = find(u, fa), fa2 = find(v, fa);
            int tmp = fa[fa1]+fa[fa2];
            if(fa[fa1] > fa[fa2]){
                fa[fa1] = fa2;
                fa[fa2] = tmp;
            }else{
                fa[fa1] = tmp;
                fa[fa2] = fa1;
            }
        }
    private:
    int dir[4][2]={{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    };

Log in to reply
 

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