题目描述
有一个 m x n 的二元网格，其中 1 表示砖块，0 表示空白。砖块 稳定（不会掉落）的前提是：
一块砖直接连接到网格的顶部，或者
至少有一块相邻（4 个方向之一）砖块 稳定 不会掉落时
给你一个数组 hits ，这是需要依次消除砖块的位置。每当消除 hits[i] = (rowi, coli) 位置上的砖块时，对应位置的砖块（若存在）会消失，然后其他的砖块可能因为这一消除操作而掉落。一旦砖块掉落，它会立即从网格中消失（即，它不会落在其他稳定的砖块上）。
返回一个数组 result ，其中 result[i] 表示第 i 次消除操作对应掉落的砖块数目。
注意，消除可能指向是没有砖块的空白位置，如果发生这种情况，则没有砖块掉落。
示例 1：
输入：grid = [[1,0,0,0],[1,1,1,0]], hits = [[1,0]]
输出：[2]
解释：
网格开始为：
[[1,0,0,0]，
[1,1,1,0]]
消除 (1,0) 处加粗的砖块，得到网格：
[[1,0,0,0]
[0,1,1,0]]
两个加粗的砖不再稳定，因为它们不再与顶部相连，也不再与另一个稳定的砖相邻，因此它们将掉落。得到网格：
[[1,0,0,0],
[0,0,0,0]]
因此，结果为 [2] 。
解题思路
逆向并查集，将官方题解加了注释，不会写。
java代码

class Solution {
    public int[] hitBricks(int[][] grid, int[][] hits) {
        int h = grid.length, w = grid[0].length;
        //创建一个并查集类数组（每块砖对应图中的一个点）
        UnionFind uf = new UnionFind(h * w + 1);
        //复制数组grid到status中
        int[][] status = new int[h][w];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                status[i][j] = grid[i][j];
            }
        }
        //先将需要打掉的砖块在status打掉
        for (int i = 0; i < hits.length; i++) {
            status[hits[i][0]][hits[i][1]] = 0;
        }
        //先按status的数据初始化并查集
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                //存在顶点时
                if (status[i][j] == 1) {
                    //如果为顶层顶点，则将其与顶层合并（顶层为第h*w个节点）
                    if (i == 0) {
                        uf.merge(h * w, i * w + j);
                    }
                    //如果其上方节点为1，则将其与上方节点合并
                    if (i > 0 && status[i - 1][j] == 1) {
                        uf.merge(i * w + j, (i - 1) * w + j);
                    }
                    //如果其左方节点为1，则将其与左方节点合并
                    if (j > 0 && status[i][j - 1] == 1) {
                        uf.merge(i * w + j, i * w + j - 1);
                    }
                }
            }
        }
        //方向为：上，左，下，右
        int[][] directions = {{0, 1},{1, 0},{0, -1},{-1, 0}};
        int[] ret = new int[hits.length];//初始化结果
        for (int i = hits.length - 1; i >= 0; i--) {//反方向遍历要击落的砖块
            int r = hits[i][0], c = hits[i][1];
            //如果原来就没有砖块则不需要掉落
            if (grid[r][c] == 0) {
                continue;
            }
            //获取顶层集合的节点数
            int prev = uf.size(h * w);
            //如果要击落的节点在顶层，则将其与顶层结合合并
            if (r == 0) {
                uf.merge(c, h * w);
            }
            //依次遍历四周四个节点
            for (int[] direction : directions) {
                int dr = direction[0], dc = direction[1];
                int nr = r + dr, nc = c + dc;

                if (nr >= 0 && nr < h && nc >= 0 && nc < w) {
                    //如果四周节点为1
                    if (status[nr][nc] == 1) {
                        //则将四周节点的集合与本集合合并
                        uf.merge(r * w + c, nr * w + nc);
                    }
                }
            }
            //求出顶层集合的节点数
            int size = uf.size(h * w);
            //现在合并进顶层节点的节点数就是会掉落的节点，不包括中心节点
            ret[i] = Math.max(0, size - prev - 1);
            //将本集合的该节点复原
            status[r][c] = 1;
        }
        return ret;
    }
}

class UnionFind {
    int[] f;//标记父类
    int[] sz;//标识当前集合的顶点数

    public UnionFind(int n) {
        f = new int[n];
        sz = new int[n];
        for (int i = 0; i < n; i++) {
            f[i] = i;
            sz[i] = 1;//初始化为1
        }
    }

    public int find(int x) {//寻找父类节点
        if (f[x] == x) {
            return x;
        }
        int newf = find(f[x]);
        f[x] = newf;//返回父类节点，并把当前节点的父类节点更新为最父类的节点
        return f[x];
    }

    public void merge(int x, int y) {//合并x和y
        int fx = find(x), fy = find(y);
        if (fx == fy) {//若原本在一个集合则退出
            return;
        }
        f[fx] = fy;//否则令x的父类节点的父类节点为y的父类节点
        sz[fy] += sz[fx];//并让y的父类节点的节点数加上x集合的节点数
    }

    public int size(int x) {//返回x集合的节点数
        return sz[find(x)];
    }
}