<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>

class Solution {
public:
    int getpos(int x,int y,int n,int m){
    return x*m+y+1;
}
int find(int x,vector<int> & par){
    if(par[x]==-1){
        return x;
    }
    int y=find(par[x],par);
    par[x]=y;
    
    return y;
}
void unionfind(int a,int b,vector<int> & par,vector<int>& rank,vector<int>& count){
    
    a=find(a,par);
    b=find(b,par);
   
   if(a==b){
       return;
   }
   if(rank[a]<rank[b]){
       rank[b]++;
       par[a]=b;
       count[b]=count[b]+count[a]; // joining the count of two component is important
   }
   else{
       rank[a]++;
       par[b]=a;
       count[a]=count[a]+count[b];
   }
   return;
}
vector<int> rec(vector<vector<int>> & v,vector<vector<int>> & w){
    // lets mark the hits as 2
    int i=0;
    while(i<w.size()){
        int x=w[i][0];
        int y=w[i][1];
        if(v[x][y]==1){
            v[x][y]=2;
        }
        i++;
    }
 
    int n=v.size();
    int m=v[0].size();
    int k=n*m+1;
    // now we union this 
    vector<int> par(k,-1);
    vector<int> count(k,1);
    vector<int> rank(k,1);
    
    // union the first column with 0  , as they symbolises that they are connected
    i=0;
    while(i<m){
        if(v[0][i]==1){
            int pos=i+1;
            par[pos]=0;
            count[0]++;
        }
        i++;
    }
    //update the rank of 0 , to the maximum , as we dont want to compare its rank and its the top
    rank[0]=10000;

    // now connect the rest of the 1s
    vector<vector<int>> dir={{-1,0},{1,0},{0,1},{0,-1}};
    i=1;
    while(i<n){
        int j=0;
        while(j<m){
            if(v[i][j]==1){
                int t=0;
                while(t<4){
                    int x1=i+dir[t][0];
                    int y1=j+dir[t][1];
                    
                    if(x1>=0 && x1<n && y1>=0 && y1<m && v[x1][y1]==1){  // if the adjecent is 1 too union it .
                        int pos1 =getpos(i,j,n,m);
                        int pos2=getpos(x1,y1,n,m);
                        unionfind(pos1,pos2,par,rank,count);
                        
                    }
                    t++;
                }
            }
            j++;
        }
        i++;
    }
  
    //now that we have components with count to them . // 
    // lets move from last hit to the first hit. 
    // sa its easy to join and find , how many fell by , 
    //calculating the difference  of newcountzero -prevcountzero ...(not that tricky)
    i=w.size()-1;
    vector<int> ans(w.size(),0);
    while(i!=-1){
        int x=w[i][0]; int y=w[i][1];
        if(v[x][y]==2){
            int prevcount=count[0];
            v[x][y]=1;
            int pos=getpos(x,y,n,m);
            if(x==0){
                //that means it is at the top only
                count[0]++;
                par[pos]=0;
            }
            else{
                //lets try union with the top element
                if(v[x-1][y]==1){
                    int post=getpos(x-1,y,n,m);
                    unionfind(pos,post,par,rank,count);
                }
            }
            
            //now left and right and down
            int t=1;
            while(t<4){
                    int x1=x+dir[t][0];
                    int y1=y+dir[t][1];
                    
                    if(x1>=0 && x1<n && y1>=0 && y1<m && v[x1][y1]==1){
                        int pos1 =pos;
                        int pos2=getpos(x1,y1,n,m);
                        unionfind(pos1,pos2,par,rank,count);
                    }
                    t++;
            }
            
            //now what is the new count of top
            int newcount=count[0];
            
            int diff=max(newcount-prevcount-1,0);
            
            ans[i]=diff;
        }
        i--;
    }
    
    return ans;
}
    vector<int> hitBricks(vector<vector<int>>& v, vector<vector<int>>& w) {
        return rec(v,w);
    }
};
113175