<p>You are given an <code>n x n</code> binary matrix <code>grid</code>. You are allowed to change <strong>at most one</strong> <code>0</code> to be <code>1</code>.</p>

<p>Return <em>the size of the largest <strong>island</strong> in</em> <code>grid</code> <em>after applying this operation</em>.</p>

<p>An <strong>island</strong> is a 4-directionally connected group of <code>1</code>s.</p>

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

<pre>
<strong>Input:</strong> grid = [[1,0],[0,1]]
<strong>Output:</strong> 3
<strong>Explanation:</strong> Change one 0 to 1 and connect two 1s, then we get an island with area = 3.
</pre>

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

<pre>
<strong>Input:</strong> grid = [[1,1],[1,0]]
<strong>Output:</strong> 4
<strong>Explanation: </strong>Change the 0 to 1 and make the island bigger, only one island with area = 4.</pre>

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

<pre>
<strong>Input:</strong> grid = [[1,1],[1,1]]
<strong>Output:</strong> 4
<strong>Explanation:</strong> Can&#39;t change any 0 to 1, only one island with area = 4.
</pre>

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

<ul>
	<li><code>n == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= n &lt;= 500</code></li>
	<li><code>grid[i][j]</code> is either <code>0</code> or <code>1</code>.</li>
</ul>

class Solution {
public:
class disjointSet{
public:
    vector<int> rank,parent,size;
    // constructor
    disjointSet(int n){

        rank.resize(n+1,0);
        parent.resize(n+1);
        size.resize(n+1,1);
        for(int i=0; i<n+1; i++){
            parent[i] = i;
        }


    }

    int findUltParent(int node){
        // This function finds ultimate parent and performs path compression aswell

        if(node == parent[node]){
            return node;
        }

        return parent[node] = findUltParent(parent[node]); 
    }

    void unionByRank(int u , int v){
        int pu = findUltParent(u);
        int pv = findUltParent(v);

        if(pu == pv){
            return;
        }

        int ru = rank[pu];
        int rv = rank[pv];

        if(ru == rv){
            parent[pv] = pu;
            rank[pu] += 1;
        }
        else if(ru < rv){
            parent[pu] = pv;
        }
        else{
            parent[pv] = pu;
        }
    }

    void unionBySize(int u , int v){
        int pu = findUltParent(u);
        int pv = findUltParent(v);

        if(pu == pv){
            return;
        }

        int su = size[pu];
        int sv = size[pv];

        if(su == sv){
            parent[pv] = pu;
            size[pu] += size[pv];
        }
        else if(su < sv){
            parent[pu] = pv;
            size[pv] += size[pu];
        }
        else{
            parent[pv] = pu;
            size[pu] += size[pv];
        }
    }

    vector<int> parent_arr(){
        return parent;
    }
};
struct pair_hash {
    template <class T1, class T2>
    std::size_t operator() (const std::pair<T1, T2>& pair) const {
        return std::hash<T1>()(pair.first) ^ std::hash<T2>()(pair.second);
    }
};




    int largestIsland(vector<vector<int>>& grid) {
        int n = grid.size();
    
        // unordered_map<pair<int,int> , int, pair_hash> m;

        // int k  = 0;

        // for(int i=0; i<n; i++){
        //     for(int j=0; j<n; j++){
        //         m[{i,j}] = k;
        //         k++;
        //     }
        // }

        disjointSet ds(n*n);
        //vector<int> vis(k,-1);
        int row_arr[4] = {0,0,1,-1};
        int col_arr[4] = {1,-1,0,0};
        
        vector<int> one_arr;
        vector<pair<int,int>> zero_arr;
        // Initital configuration of disjoint set
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                
                int node = n * i + j;
                
                if(grid[i][j] == 0){
                    zero_arr.push_back({i,j});
                    continue;
                }

                one_arr.push_back(node);
                

                for(int k = 0; k<4; k++){

                    int row = i + row_arr[k];
                    int col = j + col_arr[k];
                    int adj_node = n * row + col;

                    if(row>=0 && col>=0 && row<n && col<n && grid[row][col] == 1){
                        //ds.unionByRank(node,adj_node);
                        ds.unionBySize(node,adj_node);
                    }

                }
            }
        }

        // getting max island size in initial configuration using get size function.
        int maxi = INT_MIN;
        for(int i=0; i<one_arr.size(); i++){

            int node = one_arr[i];

            int ult_p = ds.findUltParent(node);
            int node_size = ds.size[ult_p];

            maxi = max(maxi , node_size);
        
        }


        for(int s=0; s<zero_arr.size(); s++){
                
            
            //int node = m[zero_arr[s]];
            int i = zero_arr[s].first;
            int j = zero_arr[s].second;
            int node = n*i + j;
            
            unordered_set<int> neighbours;

            for(int k = 0; k<4; k++){
            
                int row = i + row_arr[k];
                int col = j + col_arr[k];
                int adj_node = n*row + col;
            
                if(row>=0 && col>=0 && row<n && col<n && grid[row][col] == 1){
                    neighbours.insert(ds.findUltParent(adj_node));
                    
                }
            }
            
            int island_size = 1;        
            
            for(int component : neighbours){
                island_size += ds.size[component];
            
            }
            
            maxi = max(island_size , maxi);
            
        }

        return maxi;
    }
};  
188690