Untitled

class Solution {
public:
    unordered_map<int, int>parent;
    int find(int a){
        return parent[a] == a?a:parent[a] = find(parent[a]);
    }
    int combine(int a, int b){
        int pa = find(a), pb = find(b);
        if(pa == pb)
            return 0;
        parent[pa] = pb;
        return 1;
    }
    vector<int> numIslands2(int m, int n, vector<vector<int>>& positions) {
        vector<int>ans;
        int comp = 0;
        int row_dir[2] = {1, -1};//Move in the same row
        int col_dir[2] = {n, -n};//Move in the same column
        for(auto p: positions){
            int coord = p[0]*n+p[1];
            if(parent.count(coord)){//Already exists
                ans.push_back(comp);
                continue;
            }
            comp++;
            parent[coord] = coord;
            for(int i = 0; i < 2; i++){
                int new_coord = coord+row_dir[i];
                if(new_coord/n != coord/n)//Not in the same row
                    continue;             //Avoid the flaw of using single num
                if(parent.count(new_coord))
                    comp -= combine(coord, new_coord);
            }
            for(int i = 0; i < 2; i++){
                int new_coord = coord+col_dir[i];
                if(parent.count(new_coord))
                    comp -= combine(coord, new_coord);
            }
            ans.push_back(comp);
        }
        return ans;
    }
    //Time O(m*n)
    //Space O(m*n)
};