<p>You are given an <code>m x n</code> binary matrix <code>grid</code>. An island is a group of <code>1</code>&#39;s (representing land) connected <strong>4-directionally</strong> (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.</p>

<p>The <strong>area</strong> of an island is the number of cells with a value <code>1</code> in the island.</p>

<p>Return <em>the maximum <strong>area</strong> of an island in </em><code>grid</code>. If there is no island, return <code>0</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/05/01/maxarea1-grid.jpg" style="width: 500px; height: 310px;" />
<pre>
<strong>Input:</strong> grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
<strong>Output:</strong> 6
<strong>Explanation:</strong> The answer is not 11, because the island must be connected 4-directionally.
</pre>

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

<pre>
<strong>Input:</strong> grid = [[0,0,0,0,0,0,0,0]]
<strong>Output:</strong> 0
</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;= 50</code></li>
	<li><code>grid[i][j]</code> is either <code>0</code> or <code>1</code>.</li>
</ul>

class Solution {
public:
    vector<int> dx;
    vector<int> dy;
    vector<vector<int>> size;
    vector<vector<pair<int, int>>> parent;
    // int bfs(vector<vector<int>>& grid, int r, int c) {
    //     int result = 0;
    //     queue<pair<int, int>> q1;
    //     q1.push({r, c});

    //     grid[r][c] = 2;
    //     while (!q1.empty()) {
    //         pair<int, int> p = q1.front();
    //         q1.pop();
    //         result++;
    //         int i = p.first;
    //         int j = p.second;
    //         cout << i << " " << j << endl;

    //         for (int k = 0; k < 4; k++) {
    //             if (i + dx[k] >= 0 && i + dx[k] < grid.size() &&
    //                 j + dy[k] >= 0 && j + dy[k] < grid[0].size() &&
    //                 grid[i + dx[k]][j + dy[k]] == 1) {
    //                 q1.push({i + dx[k], j + dy[k]});
    //                 grid[i + dx[k]][j + dy[k]] = 2;
    //             }
    //         }
    //     }
    //     return result;
    // }

    void merge (int i , int j , int i2 , int j2){
        int s1 = size[i][j];
        int s2 = size[i2][j2];
        if (i==i2 && j==j2){
            return ;
        }
        if (s1>=s2){
            parent[i2][j2]= {i, j};
            size[i][j]+= s2;
        }
        else if (s2>s1){
            parent[i][j]= {i2, j2};
            size[i2][j2]+= s1;
        }
    }
    pair<int, int> up(int i , int j){
        if (parent[i][j].first ==i && parent[i][j].second==j) return {i,j};
        return parent[i][j] = up (parent[i][j].first , parent[i][j].second);
    }
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int result = 0;
        dx = {1, 0, -1, 0};
        dy = {0, 1, 0, -1};
        size.resize(grid.size(), vector<int> (grid[0].size()));
        parent.resize(grid.size(), vector<pair<int, int>> (grid[0].size()));

        // for (int i = 0; i < grid.size(); i++) {
        //     for (int j = 0; j < grid[0].size(); j++) {
        //         if (grid[i][j] == 1) {
        //             int temp = bfs(grid, i, j);
        //             cout << temp << " ";
        //             result = max(result, temp);
        //         }
        //     }
        // }

        for (int i =0 ;i<grid.size();i++){
            for (int  j=0 ;j<grid[0].size();j++){
                size[i][j]=1;
                parent[i][j]={i,j};
            }
        }

        for (int i =0 ;i<grid.size();i++){
            for (int  j=0 ;j<grid[0].size();j++){
                if (grid[i][j]==1){
                    pair<int, int> up1 = up(i, j);
                    for (int k =0 ;k<2;k++){
                       if (i + dx[k] >= 0 && i + dx[k] < grid.size() &&
                        j + dy[k] >= 0 && j + dy[k] < grid[0].size() &&
                        grid[i + dx[k]][j + dy[k]] == 1){
                            pair<int, int> up2 = up(i+dx[k], j+dy[k]);
                            merge(up1.first , up1.second , up2.first,up2.second);
                        }
                    }
                }
            }
        }
        for (int i =0 ;i<grid.size();i++){
            for (int  j=0 ;j<grid[0].size();j++){
                if (grid[i][j]==1) result = max (result , size[i][j]);
            }
        }

        return result;
    }
};
28630