<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 DisjointSet
{
private:
    vector<int> parent, rank;

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

    int find(int x)
    {
        if (parent[x] != x)
        {
            parent[x] = find(parent[x]); // Path compression
        }
        return parent[x];
    }
    bool SameSet(int x, int y)
    {
        return find(x) == find(y);
    }
    void unite(int x, int y)
    {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY)
        {
            if (rank[rootX] > rank[rootY])
            {
                parent[rootY] = rootX;
            }
            else if (rank[rootX] < rank[rootY])
            {
                parent[rootX] = rootY;
            }
            else
            {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
};
class Solution {
public:
    vector<int> delRow={-1,0,1,0};
    vector<int> delCol={0,1,0,-1};
    int largestIsland(vector<vector<int>>& grid) {
        int n = grid.size();
        // DisjointSet ds(n*n);
        // map<int,int>mp;
        // for(int i=0;i<n;i++){
        //     for(int j=0;j<n;j++){
        //         if(grid[i][j]){
        //             for(int k=0;k<4;k++){
        //                 int nrow=i+delRow[k];
        //                 int ncol=j+delCol[k];
        //                 if(nrow>=0 and nrow<n and ncol>=0 and ncol<n and grid[nrow][ncol]){
        //                     ds.unite(n*i+j,n*nrow+ncol);
        //                 }
        //             }
        //         }
        //     }
        // }
        // // Calculate the size of each component
        // for (int i = 0; i < n; i++)
        // {
        //     for (int j = 0; j < n; j++)
        //     {
        //         if (grid[i][j] == 1)
        //         {
        //             int root = ds.find(i * n + j);
        //             mp[root]++;
        //         }
        //     }
        // }
        // int maxi=0;
        // for(auto it:mp){
        //     maxi=max(maxi,it.second);
        // }
        // for(int i=0;i<n;i++){
        //     for(int j=0;j<n;j++){
        //         if(grid[i][j]==0){
        //             set<int> uniqueIslands;
        //             for (int k = 0; k < 4; k++)
        //             {
        //                 int ni = i + delRow[k];
        //                 int nj = j + delCol[k];
        //                 if (ni >= 0 && ni < n && nj >= 0 && nj < n && grid[ni][nj] == 1)
        //                 {
        //                     uniqueIslands.insert(ds.find(ni * n + nj));
        //                 }
        //             }
        //             int potentialSize = 1;
        //             for (int island : uniqueIslands)
        //             {
        //                 potentialSize += mp[island];
        //             }
        //             maxi = max(maxi, potentialSize);
        //         }
        //     }
        // }
        // return maxi;



        //using DFS
        map<int,int>componentSize;
        function<void(int,int,int)>dfs=[&](int r,int c,int color)->void{
            if (r < 0 || r == n || c < 0 || c == n || grid[r][c] != 1) return;
            componentSize[color]++;
            grid[r][c]=color;
            for(int i=0;i<4;i++){
                int nrow = r+delRow[i];
                int ncol = c+delCol[i];
                dfs(nrow,ncol,color);
            }
        };
        int ans=1;
        int color=2;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]!=1){
                    continue;
                }
                //coloring those cell by color and increment the color to color next compoent by different color.
                dfs(i,j,color++);
                //storing the size of component
                ans=max(ans,componentSize[color-1]);
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                //skipping non-zero elements
                if(grid[i][j]!=0)continue;
                //considering 0 elements only.
                set<int> neighbours;
                for(int k=0;k<4;k++){
                    int nrow = i+delRow[k];
                    int ncol = j+delCol[k];
                    //inserting the non-zero neighbours.
                    if(nrow>=0 and nrow<n and ncol>=0 and ncol<n and grid[nrow][ncol]){
                        neighbours.insert(grid[nrow][ncol]);
                    }
                }
                //finding the size of neighbours and storing the maximum ans;
                int sz=1;
                for(auto it:neighbours){
                    sz+=componentSize[it];
                    ans=max(ans,sz);
                }
            }
        }
        return ans;
    }
};
103640