<p>Given a 2D&nbsp;<code>grid</code> consists of <code>0s</code> (land)&nbsp;and <code>1s</code> (water).&nbsp; An <em>island</em> is a maximal 4-directionally connected group of <code><font face="monospace">0</font>s</code> and a <em>closed island</em>&nbsp;is an island <strong>totally</strong>&nbsp;(all left, top, right, bottom) surrounded by <code>1s.</code></p>

<p>Return the number of <em>closed islands</em>.</p>

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

<p><img alt="" src="https://assets.leetcode.com/uploads/2019/10/31/sample_3_1610.png" style="width: 240px; height: 120px;" /></p>

<pre>
<strong>Input:</strong> grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
<strong>Output:</strong> 2
<strong>Explanation:</strong> 
Islands in gray are closed because they are completely surrounded by water (group of 1s).</pre>

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

<p><img alt="" src="https://assets.leetcode.com/uploads/2019/10/31/sample_4_1610.png" style="width: 160px; height: 80px;" /></p>

<pre>
<strong>Input:</strong> grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
<strong>Output:</strong> 1
</pre>

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

<pre>
<strong>Input:</strong> grid = [[1,1,1,1,1,1,1],
&nbsp;              [1,0,0,0,0,0,1],
&nbsp;              [1,0,1,1,1,0,1],
&nbsp;              [1,0,1,0,1,0,1],
&nbsp;              [1,0,1,1,1,0,1],
&nbsp;              [1,0,0,0,0,0,1],
               [1,1,1,1,1,1,1]]
<strong>Output:</strong> 2
</pre>

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

<ul>
	<li><code>1 &lt;= grid.length, grid[0].length &lt;= 100</code></li>
	<li><code>0 &lt;= grid[i][j] &lt;=1</code></li>
</ul>

class DisjointSet{
    public:
    vector<int>size,parent;
    DisjointSet(int n){
        size.resize(n+1,1);
        parent.resize(n+1);
        for(int i=0;i<=n;i++)parent[i]=i;
    }
    int findUpar(int node){
        if(node==parent[node])return node;
        return parent[node]=findUpar(parent[node]);
    }
    void unionBySize(int u,int v){
        int up=findUpar(u);
        int vp=findUpar(v);
        if(up==vp)return;
        if(size[up]<size[vp]){
            parent[up]=vp;
            size[vp]+=size[up];
        }
        else{
            parent[vp]=up;
            size[up]+=size[vp];
        }
    }
};
class Solution {
public:
    int closedIsland(vector<vector<int>>& grid) {
        int n=grid.size(),m=grid[0].size();
        vector<pair<int,int>>directions={{-1,0},{1,0},{0,-1},{0,1}};

        for(int i=0;i<n;i++){

            if(!grid[i][0])dfs(i,0,n,m,directions,grid);

            if(!grid[i][m-1])dfs(i,m-1,n,m,directions,grid);
        }

        for(int i=0;i<m;i++){

            if(!grid[0][i])dfs(0,i,n,m,directions,grid);

            if(!grid[n-1][i])dfs(n-1,i,n,m,directions,grid);
        }

        DisjointSet ds(n*m);

        set<int>st;

        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                int node=i*m+j;
                if(grid[i][j])continue;
                for(auto& [dr,dc]:directions){
                    int nr=i+dr;
                    int nc=j+dc;
                    int adjNode=nr*m+nc;
                    if(nr>=0 && nr<n && nc>=0 && nc<m && !grid[nr][nc]){
                        if(ds.findUpar(node)!=ds.findUpar(adjNode))ds.unionBySize(node,adjNode);
                    }
                }
                st.insert(ds.findUpar(node));
            }
        }


        set<int>result;

        for(auto i:st)result.insert(ds.findUpar(i));

        // for(int i=0;i<n;i++){
        //     for(int j=0;j<m;j++){
        //         if(!grid[i][j])st.insert(ds.findUpar(i*m+j));
        //     }
        // }

        return result.size();
    }
    void dfs(int r,int c,int n,int m,vector<pair<int,int>>&directions,vector<vector<int>>&grid){
        grid[r][c]=1;
        for(auto&[dr,dc]:directions){
            int nr=r+dr;
            int nc=c+dc;
        
            if(nr>=0 && nr<n && nc>=0 && nc<m && !grid[nr][nc])dfs(nr,nc,n,m,directions,grid);
        }
    }
};

13624