305

class UnionFind{
public:
    vector<int> parent, rank;
    vector<bool> vis;
    int components;

    UnionFind(int n){
        parent.resize(n);
        vis.assign(n, false);
        for(int i=0; i<n; i++)
            parent[i] = i;
        rank.assign(n, 0);
        components = 0;
    }

    int find(int x){
        return (x == parent[x]) ? x : (parent[x] = find(parent[x]));
    }

    void unionSet(int x, int y){
        if(!vis[x] || !vis[y]) return;
        int px = find(x);
        int py = find(y);
        if(px != py){
            components--;
            if(rank[px] > rank[py]){
                parent[py] = px;
            }
            else{
                parent[px] = py;
                rank[py]++;
            }
        }
    }

    void markVisited(int x){
        vis[x] = true;
    }
};

class Solution {

public:
    vector<int> numIslands2(int m, int n, vector<vector<int>>& positions) {
        UnionFind uf = UnionFind(m*n);
        vector<int> ans;
        for(auto edge: positions){
            int x = edge[0], y = edge[1];
            if(!uf.vis[x*n+y]){
                uf.components++;
                uf.markVisited(x*n+y);
            }
            if(x-1 >= 0){
                int  hash = (x-1)*n+y;
                uf.unionSet(x*n+y, hash);
            }
            if(y-1 >= 0){
                int hash = x*n + y-1;
                uf.unionSet(x*n+y, hash);
            }
            if(x+1 < m){
                int hash = (x+1)*n+y;
                uf.unionSet(x*n+y, hash);
            }
            if(y+1 < n){
                int hash = x*n + y+1;
                uf.unionSet(x*n+y, hash);
            }
            ans.push_back(uf.components);
        }

        return ans;
    }
};