<p>You are given an <code>m x n</code> binary <code>grid</code>, where each <code>1</code> represents a brick and <code>0</code> represents an empty space. A brick is <strong>stable</strong> if:</p>

<ul>
	<li>It is directly connected to the top of the grid, or</li>
	<li>At least one other brick in its four adjacent cells is <strong>stable</strong>.</li>
</ul>

<p>You are also given an array <code>hits</code>, which is a sequence of erasures we want to apply. Each time we want to erase the brick at the location <code>hits[i] = (row<sub>i</sub>, col<sub>i</sub>)</code>. The brick on that location&nbsp;(if it exists) will disappear. Some other bricks may no longer be stable because of that erasure and will <strong>fall</strong>. Once a brick falls, it is <strong>immediately</strong> erased from the <code>grid</code> (i.e., it does not land on other stable bricks).</p>

<p>Return <em>an array </em><code>result</code><em>, where each </em><code>result[i]</code><em> is the number of bricks that will <strong>fall</strong> after the </em><code>i<sup>th</sup></code><em> erasure is applied.</em></p>

<p><strong>Note</strong> that an erasure may refer to a location with no brick, and if it does, no bricks drop.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> grid = [[1,0,0,0],[1,1,1,0]], hits = [[1,0]]
<strong>Output:</strong> [2]
<strong>Explanation: </strong>Starting with the grid:
[[1,0,0,0],
 [<u>1</u>,1,1,0]]
We erase the underlined brick at (1,0), resulting in the grid:
[[1,0,0,0],
 [0,<u>1</u>,<u>1</u>,0]]
The two underlined bricks are no longer stable as they are no longer connected to the top nor adjacent to another stable brick, so they will fall. The resulting grid is:
[[1,0,0,0],
 [0,0,0,0]]
Hence the result is [2].
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> grid = [[1,0,0,0],[1,1,0,0]], hits = [[1,1],[1,0]]
<strong>Output:</strong> [0,0]
<strong>Explanation: </strong>Starting with the grid:
[[1,0,0,0],
 [1,<u>1</u>,0,0]]
We erase the underlined brick at (1,1), resulting in the grid:
[[1,0,0,0],
 [1,0,0,0]]
All remaining bricks are still stable, so no bricks fall. The grid remains the same:
[[1,0,0,0],
 [<u>1</u>,0,0,0]]
Next, we erase the underlined brick at (1,0), resulting in the grid:
[[1,0,0,0],
 [0,0,0,0]]
Once again, all remaining bricks are still stable, so no bricks fall.
Hence the result is [0,0].
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 200</code></li>
	<li><code>grid[i][j]</code> is <code>0</code> or <code>1</code>.</li>
	<li><code>1 &lt;= hits.length &lt;= 4 * 10<sup>4</sup></code></li>
	<li><code>hits[i].length == 2</code></li>
	<li><code>0 &lt;= x<sub>i&nbsp;</sub>&lt;= m - 1</code></li>
	<li><code>0 &lt;=&nbsp;y<sub>i</sub> &lt;= n - 1</code></li>
	<li>All <code>(x<sub>i</sub>, y<sub>i</sub>)</code> are unique.</li>
</ul>

// standard union find template, slightly modified for this question
class UnionFind {

public:

	vector<int> parent, rank, size;
    int n;
    
    UnionFind(int n){
        this->n = n;
        parent = vector<int>(n);
        rank = vector<int>(n);
		size = vector<int>(n);
        
        for(int i=0; i<n; i++){
            parent[i] = i; // parent of each node will be itself initially
            rank[i] = 0; // rank will be 0 for all nodes initially
			size[i] = 1; // size will be 1 for all nodes initially
        }
    }
    
    // finds the parent of given node u
    int find(int u) {
		// if the node is the parent of itself, then it is the root of the set 
        if(u == parent[u]){
            return u;
        }
		// else, find the parent while also compressing the paths
        return u = find(parent[u]);
    }
    
    // merges two sets into one, u and v belong to the corresponding sets
	// performs union by rank
    void unionByRank(int u, int v) {
        // find the parents of u and v
        u = find(u);
        v = find(v);
        
        // if u and v does not belong to the same set
        if(u != v){
			// if tree has lower rank
            if(rank[u] < rank[v]){
                swap(u, v);
            }
            
            // attach lower rank tree to higher rank tree
            parent[v] = u;
            
			// if the ranks become equal, then increase the rank
            if(rank[u] == rank[v]){
                rank[u]++;
            }
        }
    }

	// perform union by size
	int unionBySize(int u, int v) {
		// find the parents of u and v
		u = find(u);
		v = find(v);
        int res = 0;

		// if u and v do not belong to the same set
		if(u != v) {
            // if the bricks belonging to the set v is not stable
            if(find(v) != find(n-1)) res = size[v];

			// if size of u is smaller
			if(size[u] < size[v]) {
				swap(u, v);
			}

			// attach smaller size tree to larger size tree
			parent[v] = u;

			// the tree u now contains all the elements of v as well
			size[u] += size[v];
		}

        return res;
	}
};

class Solution {
public:
    int m, n;

    int toInd(int x, int y) {
        return n*x + y;
    }

    vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) {
        m=grid.size(), n=grid[0].size();

        // remove the nodes that are present in hits from the grid
        for(vector<int>& hit : hits) {
            int x=hit[0], y=hit[1];

            // remove the node only if it is actually present in the grid
            if(grid[x][y]==1) grid[x][y] = -1;
        }

        // create UnionFind of size m*n + 1;
        UnionFind uf(m*n + 1);

        // connect the first row nodes to the top of the grid represented by the special node m*n
        for(int i=0; i<n; i++) {
            if(grid[0][i]==1) uf.unionBySize(i, m*n);
        }

        // connect the remaining nodes
        for(int i=1; i<m; i++) {
            for(int j=0; j<n; j++) {
                if(grid[i][j]==1) {
                    if(grid[i-1][j]==1) uf.unionBySize(toInd(i,j), toInd(i-1,j));
                    if(i+1<m and grid[i+1][j]==1) uf.unionBySize(toInd(i,j), toInd(i+1,j));
                    if(j-1>=0 and grid[i][j-1]==1) uf.unionBySize(toInd(i,j), toInd(i,j-1));
                    if(j+1<n and grid[i][j+1]==1) uf.unionBySize(toInd(i,j), toInd(i,j+1));
                }
            }
        }

        // reverse the hits
        reverse(hits.begin(), hits.end());

        // now add the nodes deleted by hits one by one and check the number of nodes that become stable
        vector<int> result;

        for(vector<int>& hit : hits) {
            int x=hit[0], y=hit[1];

            // if the node was not present in the initial grid
            if(grid[x][y] != -1) {
                result.push_back(0);
                continue;
            }

            // add the node back to the grid
            grid[x][y] = 1;

            // check if the node belongs to the first row, if true then connect it to the special node m*n
            if(x == 0) uf.unionBySize(toInd(x,y), m*n);

            // the number of nodes that belong to the adjacent non-stable components
            int count = 0;

            // connect the current node to the adjacent nodes
            if(x-1>=0 and grid[x-1][y]==1) count += uf.unionBySize(toInd(x,y),toInd(x-1,y));
            if(x+1<m and grid[x+1][y]==1) count += uf.unionBySize(toInd(x,y),toInd(x+1,y));
            if(y-1>=0 and grid[x][y-1]==1) count += uf.unionBySize(toInd(x,y),toInd(x,y-1));
            if(y+1<n and grid[x][y+1]==1) count += uf.unionBySize(toInd(x,y),toInd(x,y+1));

            // if the current node became stable or was already stable
            if(uf.find(toInd(x,y)) == uf.find(m*n)) result.push_back(count);
            else result.push_back(0);
        }

        reverse(result.begin(), result.end());

        return result;
    }
};
114425