<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>

# define    endl        "\n"
# define    sp          " "
# define    pb          push_back
# define    mp          make_pair
# define    ft          first
# define    sd          second
# define    fr(i,a,b)   for(int i=a;i<b;i++)
# define    deb(x)      cout<<#x<<" "<<x<<endl;
# define    all(x)      (x).begin(), (x).end()
# define    show(A)     for (auto i: A) cout << i << " "; cout << '\n';
# define    show_(A, n) fr(i,0,n) { show(A[i]) }
# define    SZ(x)       int(x.size())
# define    as(n,a,b)   assert(a<=n && n<=b);
# define    TIME        cerr<<"Time Taken: "<<(float)clock()/CLOCKS_PER_SEC*1000<<" ms "
# define    memset0(a)  memset((a),0,sizeof (a))
# define    memset1(a)  memset((a),-1,sizeof (a))
# define    MAX         ((int)1e9 + 10)
const int   MOD =       1e9 + 7;

typedef long long                                        ll;
typedef unsigned long long                               llu;
typedef long double                                      ld;
typedef vector < int >                                   vi;
typedef pair <int, int>                                  pii;
typedef pair <pii, int>                                  ppi;
typedef pair <int, pii>                                  pip;
typedef pair <pii, pii>                                  ppp;
typedef pair <ll, ll>                                    pll;

// inline int GCD(int a, int b) { return b == 0 ? a : GCD(b, a % b); }
// inline int LCM(int a, int b) { return a * b / GCD(a, b); }
// inline int ceil(int a, int b){  return (a%b==0) ? a/b : a/b +1 ;}
// inline int logb(int base,int num){ return log(num)/log(base);}
// const int mod = 1e9 + 7;
// inline int power(int x, int y){ if(y==0)return 1;x%=mod;if(y%2)return (x*power(x*x, y/2))%mod;return power(x*x, y/2)%mod;}

class DisjointSet {
public:
    int n;
    // contains parent as +ve and size as -ve
    vector<int> sz;

    DisjointSet(int n) {
        sz.resize(n+1, -1);
    }

    int findPar(int v) {
        if(v<0)     //invalid
            return v;

        if(sz[v] < 0)
            return v;

        return sz[v] = findPar(sz[v]);
    }

    bool unionBySize(int u, int v) {

        int pu = findPar(u);
        int pv = findPar(v);

        if(pu == pv)
            return 0;

        if(sz[pu] < sz[pv]){
            sz[pu] += sz[pv];
            sz[pv] = pu;    //parent
        } else {
            sz[pv] += sz[pu];
            sz[pu] = pv;    //parent
        }

        return 1;
    }
};

class Solution {
public:
    int largestIsland(vector<vector<int>>& grid) {
        int n = SZ(grid);
        int dir2[] = {1,0,1};
        int dir4[] = {1,0,-1,0,1};

        DisjointSet ds(n*n);

        fr(i,0,n){
            fr(j,0,n){
                if(grid[i][j]){
                    fr(k,0,2){
                        int x = i+dir2[k];
                        int y = j+dir2[k+1];

                        if(x<n && y<n && grid[x][y]){
                            ds.unionBySize(n*i+j, n*x+y);
                        }
                    }
                }
            }
        }

        int ans=0;
        fr(i,0,n){
            fr(j,0,n){
                if(!grid[i][j]) {
                    set<int> par;
                    int cur=1;
                    fr(k,0,4){
                        int x = i+dir4[k];
                        int y = j+dir4[k+1];

                        if(x>=0 && x<n && y>=0 && y<n && grid[x][y]){
                            par.insert(ds.findPar(n*x+y));
                        }
                    }

                    for(const int &k: par) {
                        cur-=ds.sz[k];
                    }

                    ans = max(ans, cur);
                }
            }
        }

        if(!ans) {
            ans = max(ans, -ds.sz[ds.findPar(0)]);
        }

        return ans;
    }
};
103640