<p>You are given an <code>m x n</code> binary grid <code>grid</code> where <code>1</code> represents land and <code>0</code> represents water. An <strong>island</strong> is a maximal <strong>4-directionally</strong> (horizontal or vertical) connected group of <code>1</code>&#39;s.</p>

<p>The grid is said to be <strong>connected</strong> if we have <strong>exactly one island</strong>, otherwise is said <strong>disconnected</strong>.</p>

<p>In one day, we are allowed to change <strong>any </strong>single land cell <code>(1)</code> into a water cell <code>(0)</code>.</p>

<p>Return <em>the minimum number of days to disconnect the grid</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/12/24/land1.jpg" style="width: 500px; height: 169px;" />
<pre>
<strong>Input:</strong> grid = [[0,1,1,0],[0,1,1,0],[0,0,0,0]]

<strong>Output:</strong> 2
<strong>Explanation:</strong> We need at least 2 days to get a disconnected grid.
Change land grid[1][1] and grid[0][2] to water and get 2 disconnected island.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/12/24/land2.jpg" style="width: 404px; height: 85px;" />
<pre>
<strong>Input:</strong> grid = [[1,1]]
<strong>Output:</strong> 2
<strong>Explanation:</strong> Grid of full water is also disconnected ([[1,1]] -&gt; [[0,0]]), 0 islands.
</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;= 30</code></li>
	<li><code>grid[i][j]</code> is either <code>0</code> or <code>1</code>.</li>
</ul>

// if already 0/multiple connected components, return 0 -> we can build the adj list for AP too at the same time
// then its either 1 or 2 left to remove
// if you can remove 1 to disconnect the rest of the graph, its an articulation point, so if there exists articulation point, return 1, otherwise 2
// we can compress the x and y coords into 1 number by taking hash = x*100 + y, given hash, y = hash%100, x = hash/100

class Solution {
public:
    int height[3031]; // 30*100 + 31 is the max coord, we just leave it as that
    int dp[3031]; //dp[x] is number of back edges passing over the edge of x and its parent
    bool dfs(int curr, int par, vector<vector<int>>&adj){ 
        //use true to indicate AP found and do early return
        int cnt=0,prev=0;
        for(const auto &child:adj[curr]){
            if(!height[child]){ // 0 indicates not vis before
                height[child]=height[curr]+1;
                bool res=dfs(child,curr,adj);
                if(res)return true; //do early return, AP has been found
                //number of backedges should be the sum of the number of backedges of all its children, EXCEPT for the backedges that lead to itself, but we will handle that when we come across it
                dp[curr]+=dp[child]; 
                if(dp[curr]==prev)cnt++; //AP because the curr node has a child that has no backedges leading above itself
            }
            else if(height[child]<height[curr]){
                // the child has alr been visited, and its an ancestor of it, this is a back edge
                dp[curr]++; //there is a backedge leading from this to the child, that passes over its direct parent
                dp[child]--; //its child had a back edge being calculated (since the "child" has the value from its child, which includes the backedge to itself, being counted. this is a bad edge, and we remove it)
            }
            prev=dp[curr];
        }
        // if it is a root, it should have more than one child node
        // otherwise, if there is at least one AP, we can early return
        return ((par==-1&&cnt>1)||(par!=-1&&cnt));
    }
    bool hasArticulationPoint(vector<vector<int>>&adj, int root){
        height[root]=1;
        if(adj[root].size()==0)return true; //edge case of only 1 node
        return dfs(root,-1,adj);
    }
    int minDays(vector<vector<int>>& grid) {
        const int dx[]={0,1,0,-1};
        const int dy[]={1,0,-1,0};
        auto hash=[](const int &x,const int &y){return x*100+y;};
        auto unhash=[](const int &hashed){return pair<int,int>{hashed/100,hashed%100};};
        vector<vector<int>>adj(3031);
        int root=-1;
        bool vis[3031];
        memset(vis,false,sizeof(vis));
        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[0].size();j++){
                queue<int>q;
                int hashed=hash(i,j);
                if(grid[i][j]&&!vis[hashed]){ // start of a cc
                    q.push(hashed);
                    if(root==-1)root=hashed; // first cc
                    else return 0; // multiple CCs
                }
                else continue;
                vis[root]=true;
                while(!q.empty()){
                    auto temp=q.front();
                    const auto [x,y]=unhash(temp);
                    q.pop();
                    for(int k=0;k<4;k++){
                        int nx=x+dx[k];
                        int ny=y+dy[k];
                        if(nx>=0&&nx<grid.size()&&ny>=0&&ny<grid[0].size()&&grid[nx][ny]){
                            int pos=hash(nx,ny);
                            adj[temp].push_back(pos);
                            adj[pos].push_back(temp);
                            if(vis[pos])continue;
                            q.push(pos);
                            vis[pos]=true;
                        }
                    }
                }
            }
        }
        if(root==-1)return 0; // no CCs
        if(hasArticulationPoint(adj,root))return 1;
        return 2;
    }
};
32860