<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:
    def minDays(self, grid: List[List[int]]) -> int:
        def how_many_island(grid):
            ans = 0
            for i in range(rows):
                for j in range(cols):
                    if grid[i][j] == 1:
                        ans += 1
                        grid[i][j] = 0
                        dq = deque()
                        dq.append((i, j))
                        while dq:
                            x, y = dq.popleft()
                            for a, b in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):
                                if 0 <= a < rows and 0 <= b < cols and grid[a][b] == 1:
                                    grid[a][b] = 0
                                    dq.append((a, b))
            return ans
        def bfs_after_delete_node(node):
            visited = set()
            visited.add(node)
            start_node = graph[node][0]
            dq = deque()
            dq.append(start_node)
            visited.add(start_node)
            while dq:
                curr_node = dq.popleft()
                for nei in graph[curr_node]:
                    if nei not in visited:
                        visited.add(nei)
                        dq.append(nei)
            return len(visited) == total_lands      # return False only if not all nodes connect after delete one
        rows, cols = len(grid), len(grid[0])
        total_lands = 0
        for i in range(rows):
            for j in range(cols):
                total_lands += grid[i][j] == 1
        count_of_island = how_many_island(copy.deepcopy(grid))
        if count_of_island != 1:
            return 0
        if total_lands == 2:
            return 2
        if total_lands == 1:
            return 1
        graph = defaultdict(list)
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == 1:
                    for a, b in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):                        
                        if 0 <= a < rows and 0 <= b < cols and grid[a][b] == 1:                            
                            graph[(i, j)].append((a, b))      
        for node in graph:
            if len(graph[node]) == 1:
                return 1
        for node in graph:
            if not bfs_after_delete_node(node):
                return 1
        return 2




                # graph solution, work nice, but not best runtime
        # def how_many_island(grid):
        #     ans = 0
        #     for i in range(rows):
        #         for j in range(cols):
        #             if grid[i][j] == 1:
        #                 ans += 1
        #                 grid[i][j] = 0
        #                 dq = deque()
        #                 dq.append((i, j))
        #                 while dq:
        #                     x, y = dq.popleft()
        #                     for a, b in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):
        #                         if 0 <= a < rows and 0 <= b < cols and grid[a][b] == 1:
        #                             grid[a][b] = 0
        #                             dq.append((a, b))
        #     return ans
        # def bfs_after_delete_node(node):
        #     visited = set()
        #     visited.add(node)
        #     start_node = graph[node][0]
        #     dq = deque()
        #     dq.append(start_node)
        #     visited.add(start_node)
        #     while dq:
        #         curr_node = dq.popleft()
        #         for nei in graph[curr_node]:
        #             if nei not in visited:
        #                 visited.add(nei)
        #                 dq.append(nei)
        #     return len(visited) == total_lands      # return False only if not all nodes connect after delete one
        # rows, cols = len(grid), len(grid[0])
        # total_lands = 0
        # for i in range(rows):
        #     for j in range(cols):
        #         total_lands += grid[i][j] == 1
        # count_of_island = how_many_island(copy.deepcopy(grid))
        # if count_of_island != 1:
        #     return 0
        # if total_lands == 2:
        #     return 2
        # if total_lands == 1:
        #     return 1
        # graph = defaultdict(list)
        # for i in range(rows):
        #     for j in range(cols):
        #         if grid[i][j] == 1:
        #             for a, b in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):                        
        #                 if 0 <= a < rows and 0 <= b < cols and grid[a][b] == 1:                            
        #                     graph[(i, j)].append((a, b))      
        # for node in graph:
        #     if len(graph[node]) == 1:
        #         return 1
        # for node in graph:
        #     if not bfs_after_delete_node(node):
        #         return 1
        # return 2
        












            # Wrong Answer 41 / 99 testcases passed
                # check count of islands
                # if only one island: check is more the 2 land in island
                # find min number of neightbor land beetwen all lands in island
                # this solution incorrect for cases like (give ans 2, bur correct 1)
                #  11011
                #  11111
                #  11011 
        # def how_many_island(grid):
        #     ans = 0
        #     for i in range(rows):
        #         for j in range(cols):
        #             if grid[i][j] == 1:
        #                 ans += 1
        #                 grid[i][j] = 0
        #                 dq = deque()
        #                 dq.append((i, j))
        #                 while dq:
        #                     x, y = dq.popleft()
        #                     for a, b in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):
        #                         if 0 <= a < rows and 0 <= b < cols and grid[a][b] == 1:
        #                             grid[a][b] = 0
        #                             dq.append((a, b))
        #     return ans
        # def count_of_nei(i, j):
        #     ans = 0
        #     for a, b in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
        #         if 0 <= a < rows and 0 <= b < cols and grid[a][b] == 1:
        #             ans += 1
        #     return ans
        # rows, cols = len(grid), len(grid[0])
        # total_lands = 0
        # for i in range(rows):
        #     for j in range(cols):
        #         total_lands += grid[i][j] == 1
        # count_of_island = how_many_island(grid)
        # if count_of_island != 1:
        #     return 0
        # if total_lands == 2:
        #     return 2
        # if total_lands == 1:
        #     return 1
        # min_nei = 2
        # for i in range(rows):
        #     for j in range(cols):
        #         if grid[i][j] == 1:
        #            min_nei = min(min_nei, count_of_nei(i, j))
        # return min_nei

                # Wrong Answer 96 / 99 testcases passed
        # def how_many_island(grid):
        #     ans = 0
        #     for i in range(rows):
        #         for j in range(cols):
        #             if grid[i][j] == 1:
        #                 ans += 1
        #                 grid[i][j] = 0
        #                 dq = deque()
        #                 dq.append((i, j))
        #                 while dq:
        #                     x, y = dq.popleft()
        #                     for a, b in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):
        #                         if 0 <= a < rows and 0 <= b < cols and grid[a][b] == 1:
        #                             grid[a][b] = 0
        #                             dq.append((a, b))
        #     return ans
        # def count_of_nei(i, j):
        #     ans = 0
        #     for a, b in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
        #         if 0 <= a < rows and 0 <= b < cols and grid[a][b] == 1:
        #             ans += 1
        #     return ans
        # rows, cols = len(grid), len(grid[0])
        # total_lands = 0
        # for i in range(rows):
        #     for j in range(cols):
        #         total_lands += grid[i][j] == 1
        # grid_copy = [[0] * cols for _ in range(rows)]
        # for i in range(rows):
        #     for j in range(cols):
        #         grid_copy[i][j] = grid[i][j]
        # count_of_island = how_many_island(grid_copy)
        # if count_of_island != 1:
        #     return 0
        # if total_lands == 2:
        #     return 2
        # if total_lands == 1:
        #     return 1
        # rows_sm = [0] * rows
        # cols_sm = [0] * cols
        # for i in range(rows):
        #     for j in range(cols):
        #         if grid[i][j] == 1:
        #             rows_sm[i] += 1
        #             cols_sm[j] += 1
        # if 1 in rows_sm or 1 in cols_sm:
        #     return 1
        # min_nei = 2
        # for i in range(rows):
        #     for j in range(cols):
        #         if grid[i][j] == 1:
        #             min_nei = min(min_nei, count_of_nei(i, j))
        # return min_nei
                
        
        

        
307