<p>You are given an <code>m x n</code> binary matrix <code>grid</code>, where <code>0</code> represents a sea cell and <code>1</code> represents a land cell.</p>

<p>A <strong>move</strong> consists of walking from one land cell to another adjacent (<strong>4-directionally</strong>) land cell or walking off the boundary of the <code>grid</code>.</p>

<p>Return <em>the number of land cells in</em> <code>grid</code> <em>for which we cannot walk off the boundary of the grid in any number of <strong>moves</strong></em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/02/18/enclaves1.jpg" style="width: 333px; height: 333px;" />
<pre>
<strong>Input:</strong> grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
<strong>Output:</strong> 3
<strong>Explanation:</strong> There are three 1s that are enclosed by 0s, and one 1 that is not enclosed because its on the boundary.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/02/18/enclaves2.jpg" style="width: 333px; height: 333px;" />
<pre>
<strong>Input:</strong> grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
<strong>Output:</strong> 0
<strong>Explanation:</strong> All 1s are either on the boundary or can reach the boundary.
</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;= 500</code></li>
	<li><code>grid[i][j]</code> is either <code>0</code> or <code>1</code>.</li>
</ul>

class DisjointSet:
    def __init__(self,n):
        self.rank=[0]*(n+1)
        self.parent=[i for i in range(n+1)]
        self.size=[1]*(n+1)
    def find_ultimate_parent(self,node):
        if self.parent[node]==node:
            return node
        self.parent[node]=self.find_ultimate_parent(self.parent[node])
        return self.parent[node]
    def union_by_rank(self,u,v):
        up_u=self.find_ultimate_parent(u)
        up_v=self.find_ultimate_parent(v)
        if up_u==up_v:
            return
        if self.rank[up_v]>self.rank[up_u]:
            self.parent[up_u]=up_v
        elif self.rank[up_v]<self.rank[up_u]:
            self.parent[up_v]=up_u
        else:
            self.parent[up_v]=up_u
            self.rank[up_u]+=1
    def union_by_size(self,u,v):
        up_u=self.find_ultimate_parent(u)
        up_v=self.find_ultimate_parent(v)
        if up_u==up_v:
            return
        if self.size[up_u]>self.size[up_v]:
            self.size[up_u]+=self.size[up_v]
        else:
            self.size[up_v]+=self.size[up_u]

class Solution:
    def numEnclaves(self, grid: List[List[int]]) -> int:
        
        delrow=[-1,0,1,0]
        delcol=[0,1,0,-1]
        n=len(grid)
        m=len(grid[0])
        a=DisjointSet(n*m)
        vis=[[0 for i in range(m)]for j in range(n)]
        default_parent_node=set()
        track=[0]*(m*n)
        def solve(row,col,grid):
            vis[row][col]=1
            node_value=row*m+col
            for i in range(4):
                nr=delrow[i]+row
                nc=delcol[i]+col
                new_node_value=nr*m+nc
                if nr>=0 and nr<n and nc>=0 and nc<m and vis[nr][nc]==0 and grid[nr][nc]==1:
                    a.union_by_rank(node_value,new_node_value)
                    solve(nr,nc,grid)
                elif (nr<0 or nr>=n or nc<0 or nc>=m):
                    track[a.find_ultimate_parent(node_value)]=1
        number_of_ones=0
        for i in range(n):
            for j in range(m):
                if vis[i][j]==0 and grid[i][j]==1:
                    
                    solve(i,j,grid)
        for i in range(n):
            for j in range(m):
                if grid[i][j]==1 and track[a.find_ultimate_parent(i*m+j)]==0:
                    number_of_ones+=1
        return number_of_ones
        


               
43820