<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:
    void BFS(vector<vector<int>>& grid, int i, int j, vector< vector<int>>& visited, map<int,int>& index, vector< vector<int>>& graph){
        deque< pair<int,int> > dq;
        int r = 0;
        dq.push_back( {i,j} );
        visited[i][j] = 1;
        while ( !dq.empty() ){
            auto p = dq.front();
            dq.pop_front();
            if ( p.first - 1 >= 0 && grid[p.first-1][p.second] == 1 && visited[p.first-1][p.second] == 0 ) {
                visited[p.first-1][p.second] = 1;
                dq.push_back( {p.first-1, p.second} );
            }
            if ( p.first + 1 < grid.size() && grid[p.first+1][p.second] == 1 && visited[p.first+1][p.second] == 0 ) {
                dq.push_back( {p.first+1, p.second} );
                visited[p.first+1][p.second] = 1;
            }
            if ( p.second - 1 >= 0 && grid[p.first][p.second-1] == 1 && visited[p.first][p.second-1] == 0 ) {
                dq.push_back( {p.first, p.second-1} );
                visited[p.first][p.second-1] = 1;
            }
            if ( p.second + 1 < grid[0].size() && grid[p.first][p.second+1] == 1 && visited[p.first][p.second+1] == 0 ) {
                dq.push_back( {p.first, p.second+1} );
                visited[p.first][p.second+1] = 1;
            }
            
            // Builindg the Graph
            index [p.first * grid[0].size() + p.second] = r;
            r++;
            vector<int> t;
            if ( p.first - 1 >= 0 && grid[p.first-1][p.second] == 1 ) t.push_back( (p.first-1) * grid[0].size() + p.second );
            if ( p.first + 1 < grid.size() && grid[p.first+1][p.second] == 1 ) t.push_back( (p.first+1) * grid[0].size() + p.second );
            if ( p.second - 1 >= 0 && grid[p.first][p.second-1] == 1 ) t.push_back( p.first * grid[0].size() + p.second-1 );
            if ( p.second + 1 < grid[0].size() && grid[p.first][p.second+1] == 1 ) t.push_back( p.first * grid[0].size() + p.second+1 );
            graph.push_back(t);
        }
    }
    int minDays(vector<vector<int>>& grid) {
        vector< pair<int,int> > v;
        vector< vector<int>> visited( grid.size(), vector<int>( grid[0].size(), 0) );
        vector< vector<int>> graph;
        map<int,int> index;
        for(int i=0;i < grid.size() ; i++){
            for(int j=0;j < grid[0].size() ; j++){
                if ( grid[i][j] == 1 && visited[i][j] != 1 && graph.size() == 0 ){
                    BFS(grid, i, j, visited, index, graph);
                }
                if ( grid[i][j] == 1 && visited[i][j] ==0 && graph.size() != 0 ) return 0;
            }
        }
        if ( graph.size() == 0 ) return 0;
        cout<<"before\n";
        for( int i=0;i<graph.size(); i++ ){
            cout<<i<<" ";
            for ( int j=0; j < graph[i].size(); j++ ) cout<<graph[i][j]<<" ";
            cout<<endl;
        }
        for( int i=0;i<graph.size(); i++ ){
            for ( int j=0; j < graph[i].size(); j++ ) graph[i][j] = index[ graph[i][j] ];
        }
        cout<<"after\n";
        for( int i=0;i<graph.size(); i++ ){
            cout<<i<<" ";
            for ( int j=0; j < graph[i].size(); j++ ) cout<<graph[i][j]<<" ";
            cout<<endl;
        }
        if ( graph.size() == 1 ) return 1;
        for ( int i=0; i < graph.size() ; i++){
            vector<int> visited1( graph.size(), 0 );
            deque<int>dq;
            dq.push_back(graph[i][0]);
            visited1[graph[i][0]] = 1;
            while( !dq.empty() ){
                int r = dq.front();
                dq.pop_front();
                for ( int j=0; j< graph[r].size() ; j++ ){
                    if ( graph[r][j] != i && visited1[ graph[r][j] ] == 0 ){
                        dq.push_back(graph[r][j]);
                        visited1[ graph[r][j] ] = 1;
                    }
                }
            }
            for( int j=0;j<graph.size();j++ ){
                if ( j != i && visited1[j] == 0 ) return 1;
            }
        }
        return 2;
    }
};
35100