<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 DSU {
private:
    vector<int> parent, size;
public:
    DSU(int n){
        parent.resize(n);
        iota(parent.begin(), parent.end(), 0);
        size.resize(n, 1);
    }
    int findUltParent(int u){
        if (u==parent[u]) return u;
        return parent[u]=findUltParent(parent[u]);
    }
    void unionBySize(int u, int v){
        int ulp_u=parent[u], ulp_v=parent[v];
        if (ulp_u==ulp_v) return;
        if (size[ulp_u]<size[ulp_v]){
            size[ulp_v]+=size[ulp_u];
            parent[ulp_u]=ulp_v;
        } else {
            size[ulp_u]+=size[ulp_v];
            parent[ulp_v]=ulp_u;
        }
    }
    int getSize(int u) {
        return size[u];
    }
};

class Solution {
public:
    int largestIsland(vector<vector<int>>& grid) {
        int n=grid.size(), m=grid[0].size();
        int ans=1;
        DSU ds(n*m+1);
        for (int i=0;i<n;i++){
            for (int j=0;j<n;j++){
                if (grid[i][j]){
                    int currNode=i*m+j;
                    vector<int> dirs={0, 1, 0, -1, 0};
                    if (grid[i][j]){
                        for (int d=0;d<4;d++){
                            int p=i+dirs[d], q=j+dirs[d+1];
                            int adjNode=p*m+q;
                            if (p<n&&q<n&&p>=0&&q>=0&&ds.findUltParent(adjNode)!=ds.findUltParent(currNode)){
                                if (grid[p][q]) ds.unionBySize(adjNode, currNode);
                                ans=max(ans, ds.getSize(ds.findUltParent(currNode)));   
                            }
                        } 
                    }
                }
            }
        }
        for (int i=0;i<n;i++){
            for (int j=0;j<m;j++){
                int currNode=i*m+j;
                vector<int> dirs={0, 1, 0, -1, 0};
                if (!grid[i][j]) {
                    int size=1;
                    vector<int> otherNodes;
                    for (int d=0;d<4;d++){
                        int p=i+dirs[d], q=j+dirs[d+1];
                        int adjNode=p*m+q;
                        if (p<n&&q<n&&p>=0&&q>=0&&grid[p][q]){
                            bool yes=true;
                            for (auto nod: otherNodes){
                                if (ds.findUltParent(adjNode)==ds.findUltParent(nod)) {yes=false; break;}
                            }
                            if (yes) size+=ds.getSize(ds.findUltParent(adjNode));
                            ans=max(ans, size);
                            otherNodes.push_back(adjNode);
                        }
                    }
                }
            }
        }
        return ans;
    }
};
202865