ez DFS, BFS vs UnionFind||C++ beats 100%
Intuition1st approach uses DFS.
2nd approach uses BFS.
3rd  approach uses UnionFind
This problem has the identical solution with 695. Max Area of Island
 thanks
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
1st approach uses DFS.
2nd approach uses BFS.
3rd  approach uses UnionFind
This problem has the identical solution with [695. Max Area of Island
](https://leetcode.com/problems/max-area-of-island/solutions/3548861/easy-c-solution-using-dfs-recursion/) thanks to comments by @Sergei.
# Approach
<!-- Describe your approach to solving the problem. -->
1. Declare `d[5]={0, 1, 0, -1, 0}` as a memeber variable for 4 directions
2. let `n, m` be member variables
3. Define the recursive dfs function as follows
```
int dfs(int i, int j, vector<vector<int>>& grid){
    int fish=grid[i][j];//obtain the fish in cell (i, j)
    grid[i][j]=0;// visited
    for (int a=0; a<4; a++){// 4 adjacent cells
        int r=i+d[a],  c=j+d[a+1]; //adjacent cell (r,c)
        if (r<0 || r>=n || c<0 || c>=m || grid[r][c]==0)
            continue; // outside or visited
        fish+=dfs(r, c, grid);// recursive call
    }
    return fish;
}
```
4. in `int findMaxFish(vector<vector<int>>& grid)` let `n=|grid|, m=|m=grid[0]` by the matrix convention
5. Proceed the double loop 
`if (grid[i][j]>0)
                    ans=max(ans, dfs(i, j, grid)) for i, j`
6. return `ans`
7. BFS is done.
# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
 $$O(nm)$$ 
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
$$O(nm)$$ 
# Code DFS||C++ 0ms beats 100%
```cpp []
class Solution {
public:
    const int d[5]={0, 1, 0, -1, 0};
    int n, m;
    int dfs(int i, int j, vector<vector<int>>& grid){
        int fish=grid[i][j];
        grid[i][j]=0;// visited
        for (int a=0; a<4; a++){
            int r=i+d[a],  c=j+d[a+1];
            if (r<0 || r>=n || c<0 || c>=m || grid[r][c]==0)
                continue;
            fish+=dfs(r, c, grid);
        }
        return fish;
    }
    int findMaxFish(vector<vector<int>>& grid) {
        n=grid.size(), m=grid[0].size();
        int ans=0;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if (grid[i][j]>0)
                    ans=max(ans, dfs(i, j, grid));
            }
        }
        return ans;
    }
};
```
# Standard Grid/Matrix/Graph problems can solved with DFS/BFS
There are many such kinds of such problem in Leetcode. The fastest way to implement is DFS, & then BFS. If the graph is undirected, some of them can be solved even by UnionFind; but some of them needs more tricks.

The question [1992. Find All Groups of Farmland](https://leetcode.com/problems/find-all-groups-of-farmland/solutions/5047793/dfs-bfs-vs-find-rectangle-corner-74ms-beats-99-64/) is solved by DFS& BFS.
[Please turn on English titles]
[https://youtu.be/v-w9EF67it8?si=Tjqli8PvGjYh0t8X](https://youtu.be/v-w9EF67it8?si=Tjqli8PvGjYh0t8X)
# 2nd Approach uses BFS & sets grid[r][c]=0 as visited
```
// the bfs is called in the same way in dfs solution
int bfs(int i, int j, vector<vector<int>>& grid){
    int fish=grid[i][j];
    queue<uint8_t> q; // 10*10<256
    grid[i][j]=0;// visited
    q.push((i<<4)+j); // push packed (i, j) to q
    while(!q.empty()){
        int idx=q.front(), s=idx>>4, t=idx&15;// get (r, s)
        q.pop();
        for (int a=0; a<4; a++){// adjacent cells
            int r=s+d[a],  c=t+d[a+1];
            if (r<0 || r>=n || c<0 || c>=m || grid[r][c]==0)
                continue;// ouside or visited
            fish+=grid[r][c]; // add it to fish
            q.push((r<<4)+c); // push the packed (r, c) to q
            grid[r][c]=0;// visited
        }
    }
    return fish; 
}
```
# UnionFind is good for Undirected Graph

Time complexity for UnionFind: $$O(\alpha(nm)nm)$$ where $\alpha(\cdot)$ is the inverse Ackermann function.
Use UnionFind, one can also solve [959. Regions Cut By Slashes](https://leetcode.com/problems/regions-cut-by-slashes/solutions/5614770/unionfind-dfs-euler-theorem-v-e-f-2-beats-100/)
[https://youtu.be/cR_D4uA3g3s?si=7mIs9wQ0ifN_GoGA](https://youtu.be/cR_D4uA3g3s?si=7mIs9wQ0ifN_GoGA)
1. UnionFind uses Size optimization which has similar performance like rank optimization
2. Since the matrix is small, say at most `10x10` Unionfind brings no benefit over DFS/BFS.
3. To transvere the grids, it needs only 2 directions, i.e. righttward & downwards; for large matrix, this can save much time.
4. The implemented Union method in UnionFind will return true when 2 disjoint components are really connected by this edge, other return false.
5. The crucial part for using Union is as follow:
```
sum2=sum[rA]+sum[rB];
if (G.Union(a, b)){// connect 2 components
    rA=G.Find(a);// rA=new root for  a & b
    sum[rA]=sum2;// Put fish for root  rA
    ans=max(ans, sum2);// update ans
}
```
# Code for UnionFind
```
// union find class with size
class UnionFind {
    vector<int> root, Size;
public:
    int components;
    UnionFind(int N) : root(N), Size(N, 1), components(N) {
        iota(root.begin(), root.end(), 0);
    }

    int Find(int x) {
        if (x == root[x])
            return x;
        return root[x] = Find(root[x]); // Path compression
    }

    bool Union(int x, int y) {
        x = Find(x), y = Find(y);

        if (x == y) return 0;

        if (Size[x] > Size[y]) {
            Size[x] += Size[y];
            root[y] = x;
        } else {
            Size[y] += Size[x];
            root[x] = y;
        }
        components--;
        return 1;
    }
};

class Solution {
public:
    int n, m;
    int idx(int i, int j){ return i*m+j; }

    int findMaxFish(vector<vector<int>>& grid) {
        n=grid.size(), m=grid[0].size();
        const int N=n*m;
        vector<int> sum(N, 0);
        for(int i=0; i<n; i++)
            copy(grid[i].begin(), grid[i].end(), sum.begin()+(i*m));

        UnionFind G(N);
        int ans=0, sum2;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if (grid[i][j]>0){
                    ans=max(ans, grid[i][j]);// for 1-cell components
                    int a=idx(i, j), rA, rB, b;
                    int D=(i<n-1)?grid[i+1][j]:0, R=(j<m-1)?grid[i][j+1]:0;
                    if (D>0){// down
                        b=a+m;
                        rA=G.Find(a), rB=G.Find(b);
                        sum2=sum[rA]+sum[rB];
                        if (G.Union(a, b)){ // connect 2 components
                            rA=G.Find(a);// new root for a
                            sum[rA]=sum2;
                            ans=max(ans, sum2);
                        }
                    }
                    if (R>0){// right
                        b=a+1;
                        rA=G.Find(a), rB=G.Find(b);
                        sum2=sum[rA]+sum[rB];
                        if (G.Union(a, b)){// connect 2 components
                            rA=G.Find(a);// new root for a
                            sum[rA]=sum2;
                            ans=max(ans, sum2);
                        }
                    }      
                }
            }
        }
        return ans;
    }
};
```

['Depth-First Search', 'Breadth-First Search', 'Union Find', 'C++']