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

class Solution {
public:
    /*
        Tarjan Algorithm
        - Here we need to first make a graph of the ISLAND only
        - Now if the there are no islands then we return 0
        - If only an island of 1 cell exists we return 1
        - otherwise we run the tarjan algo
        - if the graph is disconnected already then we simply return 0
        - otherwise we find the articulation nodes
        - if there exists any articulation points then we return 1
        - else we just return 2 ------> this is because maximum of 2 cells are required to break any island
        - T(m * n) ----> we need to build the graph and iterate over the grid
        - S(m * n) ----> bounded by m * n because the entire grid can be 1
    */
    vector<int> d_x = {0, 0, -1, 1};
    vector<int> d_y = {-1, 1, 0, 0};
    int time = 0;

    int dfs1(int node, 
               unordered_map<int, vector<int>>& adjList, 
               unordered_map<int, int>& arrival, 
               unordered_map<int, int>& parent, 
               unordered_map<int, int>& lowarr, 
               vector<int>& res){
        
        arrival[node] = time++;
        lowarr[node] = arrival[node];
        bool flag = false;
        int childs = 0;
        for (auto neighbor : adjList[node]){
            if (arrival.find(neighbor) == arrival.end()){
                childs++; // we count childs only on tree edges
                int val = dfs(neighbor, adjList, arrival, parent, lowarr, res);

                if (val >= arrival[node]){ // this tells us that the child does not have back edges to my ancestors
                    flag = true;
                }
                lowarr[node] = min(lowarr[node], val);
                parent[neighbor] = node;
            }
            // this is required because we want to send back the minimum of the arrival time 
            // our subtree to our parent
            else if (neighbor != parent[node]){ 
                lowarr[node] = min(lowarr[node], arrival[neighbor]);
            }
        }
        
        // if flag is true and the current node is not the parent then I am an articulation point
        if (flag && parent[node] != -1){
            res.push_back(node);
        }

        // if I am the source then I am an articulation point if I have more than 1 tree edges
        if (parent[node] == -1 && childs > 1){
            res.push_back(node);
        }

        // cout<<"node: " << node << " sending back: " << lowarr[node] << endl;
        return lowarr[node];
    }   
    


    int dfs(int node, 
               unordered_map<int, vector<int>>& adjList, 
               unordered_map<int, int>& arrival, 
               unordered_map<int, int>& parent, 
               unordered_map<int, int>& lowestArr, 
               vector<int>& res){
        
        arrival[node] = time++;
        lowestArr[node] = arrival[node];

        bool flag = false;
        int child = 0;

        for (int neighbor : adjList[node]){
            if (arrival.find(neighbor) == arrival.end()){
                parent[neighbor] = node;
                int val = dfs(neighbor, adjList, arrival, parent, lowestArr, res);
                if (val >= arrival[node]){
                    flag = true;
                }
                lowestArr[node] = min(lowestArr[node], val);
                child++;
            }
            else if (parent[neighbor] != parent[node]){
                lowestArr[node] = min(lowestArr[node], arrival[neighbor]);
            }
        }


        if (parent[node] != -1 && flag){
            res.push_back(node);
        }

        if (parent[node] == -1 && child >= 2){
            res.push_back(node);
        }

        return lowestArr[node];
    }


    int minDays(vector<vector<int>>& grid) {
        unordered_map<int, vector<int>> adjList;
        int n = grid.size();
        int m = grid[0].size();

        for (int row = 0; row < n; row++){
            for (int col = 0; col < m; col++){
                if (grid[row][col] == 1){
                    int node = row * m + col;
                    adjList[node] = {};
                    for (int k = 0; k < 4; k++){
                        int r = row + d_x[k];
                        int c = col + d_y[k];
                        if (r >= 0 && r < n &&
                            c >= 0 && c < m &&
                            grid[r][c] == 1){
                            int neighbor = r * m + c;
                            adjList[node].push_back(neighbor);
                        }
                    }
                }
            }
        }

        int len = adjList.size();
        cout<<len<<endl;
        if (len <= 1){
            return len;
        }


        unordered_map<int, int> arrival(len);
        unordered_map<int, int> parent(len);
        unordered_map<int, int> lowestArr(len);
        vector<int> res;

        bool disconnected = false;
        for (auto &node : adjList){
            if (lowestArr.find(node.first) == lowestArr.end()){
                if (disconnected){
                    return 0;
                }
                parent[node.first] = -1;
                dfs(node.first, adjList, arrival, parent, lowestArr, res);
                disconnected = true;
            }
        }
        return res.size() >= 1 ? 1 : 2;
    }

    int minDays1(vector<vector<int>>& grid) {
        unordered_map<int, vector<int>> adjList;
        int n = grid.size();
        int m = grid[0].size();

        // build the graph
        for (int row = 0; row < n; row++){
            for (int col = 0; col < m; col++){
                if (grid[row][col] == 1){
                    int node = row * m + col; // id of the current node
                    adjList[node] = {};
                    for (int k = 0; k < 4; k++){
                        int r = row + d_x[k];
                        int c = col + d_y[k];

                        if (r >= 0 && r < n &&
                            c >= 0 && c < m &&
                            grid[r][c] == 1){
                            
                            int neighbor = r * m + c; // id of the neighbor
                            
                            adjList[node].push_back(neighbor);
                        }
                    }
                }
            }
        }

        // check if there is no islands or there is only an island of 1 cell
        int len = adjList.size();
        if (len <= 1){
            return len;
        }   

        // cout<<adjList.size()<<endl;

        unordered_map<int, int> arrival(len);
        unordered_map<int, int> parent(len);
        unordered_map<int, int> lowarr(len);
        vector<int> res;

        bool disconnected = false;
        for (auto &node : adjList){
            if (lowarr.find(node.first) == lowarr.end()){
                if (disconnected){
                    return 0;
                }
                parent[node.first] = -1;
                dfs(node.first, adjList, arrival, parent, lowarr, res);
                disconnected = true;
            }
        }
        // cout<<res.size()<<endl;
        return res.size() >= 1 ? 1 : 2;
    }
};

18300