305. Number of Islands II

由0组成的矩阵不断在不同位置添加1，两个上下左右相连的则拼在一起合并成一个联通子图，问每次添加后连通子图的数目。连通子图用并查集。每次添加后size++，上下左右查一遍并合并，新的size写进结果。

class Solution {
public:
    class UF {
    public:
        vector<int> parents;
        int size;
        UF(int N): parents(N), size(0) {
            for (int i = 0; i < N; ++i) parents[i] = i;
        }
        int find(int x) {
            while (x != parents[x]) {
                parents[x] = parents[parents[x]];
                x = parents[x];
            }
            return x;
        }

        void un(int x, int y) {
            x = find(x);
            y = find(y);
            if (x != y) {
                parents[x] = y; 
                --size;
            }
        }
    };

    vector<int> numIslands2(int m, int n, vector<vector<int>>& positions) {
        UF uf(m * n);
        vector<int> res;
        unorederd_map<int, unordered_set<int>> existed;
        vector<vector<int>> dirs({{-1, 0}, {1, 0}, {0, -1}, {0, 1}});
        for (const auto &pos : positions) {
            ++uf.size;
            for (const auto &d : dirs) {
                int x = pos[0] + d[0];
                int y = pos[1] + d[1];
                if (x >= 0 && x < m && y >= 0 && y < n && existed[x].count(y)) {
                    uf.un(x * n + y, pos[0] * n + pos[1]);
                }
            }
            existed[pos[0]].insert(pos[1]);
            res.push_back(uf.size);
        }
        return res;
    }
};