Exploring Connected Waters | c++ | Easy | DFS 🚀🚀
IntuitionThe problem can be viewed as finding the maximum sum of connected components in a grid, where each cell represents a node, and its value represents the
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The problem can be viewed as finding the maximum sum of connected components in a grid, where each cell represents a node, and its value represents the number of fish present. The goal is to explore all connected cells with non-zero values and sum their values to determine the maximum fish that can be collected in a single connected component.
# Approach
<!-- Describe your approach to solving the problem. -->
We use Depth-First Search (DFS) to traverse the grid and calculate the total number of fish in each connected component:

1. Iterate over all cells in the grid. If a cell has a value greater than 0 and has not been visited, start a DFS from that cell.

2. During the DFS:
    - Mark the current cell as visited.
    - Add the value of the current cell to the total fish count.
    - Recursively visit all valid neighboring cells (up, down, left, right) that have not been visited and contain fish.

3. Keep track of the maximum fish count encountered across all connected components.

4. Return the maximum fish count as the result.

To ensure we do not revisit cells during DFS, we maintain a visited set to track the cells that have already been processed.
# Complexity
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
- Time complexity: O(m×n)
    - Each cell is visited at most once during the DFS.
    - Here, mm and nn are the number of rows and columns in the grid.

<!-- Add your space complexity here, e.g. $$O(n)$$ -->
- Space complexity: O(m×n)
    - The visited set may store up to m×nm×n cells in the worst case.
    - The recursion stack for DFS can also go as deep as m×nm×n in the worst case (when the entire grid is a single connected component).

# Code
```cpp []
class Solution {
public:
    // DFS to calculate total fish in a connected component
    int dfs(vector<vector<int>>& grid, set<pair<int, int>> &visited, int r,
            int c) {
        // Out of bounds, no fish, or already visited
        if (r < 0 || c < 0 || r >= grid.size() || c >= grid[0].size() ||
            grid[r][c] == 0 || visited.count({r, c}) > 0)
            return 0;

        visited.insert({r, c}); // Mark current cell as visited
        int res = grid[r][c];   // Add fish at the current cell

        // Explore all four directions
        res += dfs(grid, visited, r + 1, c);
        res += dfs(grid, visited, r - 1, c);
        res += dfs(grid, visited, r, c + 1);
        res += dfs(grid, visited, r, c - 1);

        return res;
    }

    int findMaxFish(vector<vector<int>>& grid) {
        int row = grid.size(), col = grid[0].size();
        set<pair<int, int>> visited; // Tracks visited cells
        int res = 0;

        // Start DFS from each cell with fish
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                res =
                    max(res, dfs(grid, visited, i, j)); // Find the maximum fish
            }
        }
        return res;
    }
};

```
['Depth-First Search', 'Graph', 'Ordered Set', 'C++']