305. Number of Islands II

union-find O(m*n+k) time O(m*n) space

class Solution {
public:
    vector<int> numIslands2(int m, int n, vector<vector<int>>& positions) {
        parent.resize(m * n, -1); // 一定要用-1因为不是每个位置都是岛
        int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
        vector<int> res;
        for (const auto &p : positions) {
            int x = p[0] * n + p[1];
            if (parent[x] == -1) { // 竟然有重复的position。。。
                parent[x] = x;
                ++cnt;
                for (int i = 0; i < 4; ++i) {
                    if (isValid(p[0] + dr[i], p[1] + dc[i], m, n)) {
                        merge(x, (p[0] + dr[i]) * n + p[1] + dc[i]);
                    }
                }
            }
            res.push_back(cnt);
        }
        return res;
    }

    bool isValid(int r, int c, int m, int n) {
        return 0 <= r && r < m && 0 <= c && c < n && parent[r * n + c] != -1;
    }

    int find(int x) {
        while (x != parent[x]) {
            x = parent[x] = parent[parent[x]];
        }
        return x;
    }

    void merge(int x, int y) {
        int px = find(x);
        int py = find(y);
        if (px != py) {
            --cnt;
            parent[px] = py;
        }
    }

    int cnt = 0;
    vector<int> parent;
};