803. Bricks Falling When Hit

https://leetcode.com/problems/bricks-falling-when-hit/

由0和1组成的矩阵，每次给定一个1敲掉，把敲掉后不与首行的1相连通的1一并都抹除。问每次敲一共会抹除多少元素。查与之连通的元素用union find。union find适合将两个component连起来，这里却需要把连起来的拆开，并查集并无法快速支持这样的操作，要尽量把敲掉替换成并查集擅长的union操作。因此把敲掉看作倒着的补齐操作，每次补上元素后新增加与首行1相连的元素即敲掉元素所失去的元素。并查集还有个常用的小优化，即生成一个dummy src连接所有的首行1形成一个大component，这样只需要查一次src的size就知道所有与首行1连通的元素数目。

/*
 * @lc app=leetcode id=803 lang=cpp
 *
 * [803] Bricks Falling When Hit
 *
 * https://leetcode.com/problems/bricks-falling-when-hit/description/
 *
 * algorithms
 * Hard (29.14%)
 * Likes:    333
 * Dislikes: 96
 * Total Accepted:    11.6K
 * Total Submissions: 39.6K
 * Testcase Example:  '[[1,0,0,0],[1,1,1,0]]\n[[1,0]]'
 *
 * We have a grid of 1s and 0s; the 1s in a cell represent bricks.  A brick
 * will not drop if and only if it is directly connected to the top of the
 * grid, or at least one of its (4-way) adjacent bricks will not drop.
 * 
 * We will do some erasures sequentially. Each time we want to do the erasure
 * at the location (i, j), the brick (if it exists) on that location will
 * disappear, and then some other bricks may drop because of that erasure.
 * 
 * Return an array representing the number of bricks that will drop after each
 * erasure in sequence.
 * 
 * 
 * Example 1:
 * Input: 
 * grid = [[1,0,0,0],[1,1,1,0]]
 * hits = [[1,0]]
 * Output: [2]
 * Explanation: 
 * If we erase the brick at (1, 0), the brick at (1, 1) and (1, 2) will drop.
 * So we should return 2.
 * 
 * 
 * Example 2:
 * Input: 
 * grid = [[1,0,0,0],[1,1,0,0]]
 * hits = [[1,1],[1,0]]
 * Output: [0,0]
 * Explanation: 
 * When we erase the brick at (1, 0), the brick at (1, 1) has already
 * disappeared due to the last move. So each erasure will cause no bricks
 * dropping.  Note that the erased brick (1, 0) will not be counted as a
 * dropped brick.
 * 
 * 
 * 
 * Note:
 * 
 * 
 * The number of rows and columns in the grid will be in the range [1,
 * 200].
 * The number of erasures will not exceed the area of the grid.
 * It is guaranteed that each erasure will be different from any other erasure,
 * and located inside the grid.
 * An erasure may refer to a location with no brick - if it does, no bricks
 * drop.
 * 
 * 
 */
class Solution {
public:
    class UF {
        vector<int> *parents;
        vector<int> *sizes;
    public:
        UF(const int N) {
            parents = new vector<int>(N);
            sizes = new vector<int>(N, 1);
            for (int i = 0; i < N; ++i) {
               (*parents)[i] = i;
            }
        } 
        int find(int x) {
            if ((*parents)[x] != x) (*parents)[x] = find((*parents)[x]);
            return (*parents)[x];
        }
        void un(int x, int y) {
            x = find(x);
            y = find(y);
            if (x == y) return;
            (*parents)[y] = x;
            (*sizes)[x] += (*sizes)[y];
        }
        int size(int x) {
            return (*sizes)[find(x)];
        }
    };

    vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) {
        const int M = grid.size(), N = grid[0].size(), K = hits.size();
        vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for (const auto &h : hits) {
            if (grid[h[0]][h[1]] == 1) grid[h[0]][h[1]] = 2;
        }
        
        UF uf(M * N + 1);
        const auto union_around = [&](const int i, const int j) {
            for (const auto &dir : dirs) {
                const int x = i + dir[0];
                const int y = j + dir[1];
                if (x >= 0 && x < M && y >= 0 && y < N && grid[x][y] == 1) {
                    uf.un(i * N + j + 1, x * N + y + 1);
                }
            }
            if (i == 0) uf.un(0, i * N + j + 1);
        };
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (grid[i][j] != 1) continue;
                union_around(i, j); 
            }
        }
        vector<int> res(K);
        int left = uf.size(0);
        
        for (int i = K - 1; i >= 0; --i) {
            const int x = hits[i][0], y = hits[i][1];
            if (grid[x][y] == 2) {
                grid[x][y] = 1;
                union_around(x, y);
                const int new_left = uf.size(0);
                res[i] = max(new_left - left - 1, 0);
                left = new_left;
            }
        }
        return res;
    }
};