[C++] DFS | BFS | Union Find | Maximum of Water Components
Intuition\nWe can traverse only one complete component of water cells and catch all the fishes in it. Do a DFS/BFS traversal on every water component and count 
# Intuition\nWe can traverse only one complete component of water cells and catch all the fishes in it. Do a DFS/BFS traversal on every water component and count total number of fishes in that component. Take maximum of all possible water components.\n\n# Recursive DFS\n```\nclass Solution {\nprivate:\n    int countFishes(vector<vector<int>>& grid, vector<vector<bool>>& visited, int r, int c) {\n        if (r == -1 || r == grid.size() || c == -1 || c == grid[0].size() || !grid[r][c] || visited[r][c]) {\n            return 0;\n        }\n        visited[r][c] = true;\n        return grid[r][c] +\n            countFishes(grid, visited, r, c + 1) +\n            countFishes(grid, visited, r, c - 1) +\n            countFishes(grid, visited, r + 1, c) +\n            countFishes(grid, visited, r - 1, c);\n    }\n    \npublic:\n    int findMaxFish(vector<vector<int>>& grid) {\n        int m = grid.size(), n = grid[0].size(), result = 0;\n        vector visited(m, vector<bool>(n));\n        for (int i = 0; i < m; i++) {\n            for (int j = 0; j < n; j++) {\n                if (grid[i][j] && !visited[i][j]) {\n                    result = max(result, countFishes(grid, visited, i, j));\n                }\n            }\n        }\n        return result;\n    }\n};\n```\n\n# Iterative DFS\n```\nclass Solution {\nprivate:\n    vector<int> dr, dc;\n\n    int countFishes(vector<vector<int>>& grid, vector<vector<bool>>& visited, int r, int c) {\n        int m = grid.size(), n = grid[0].size(), count = 0;\n        stack<pair<int, int>> s;\n        s.push({r, c});\n        visited[r][c] = true;\n        while (!s.empty()) {\n            r = s.top().first, c = s.top().second; s.pop();\n            count += grid[r][c];\n            for (int i = 0; i < 4; i++) {\n                int r1 = r + dr[i], c1 = c + dc[i];\n                if (0 <= r1 && r1 < m && 0 <= c1 && c1 < n && grid[r1][c1] && !visited[r1][c1]) {\n                    s.push({r1, c1});\n                    visited[r1][c1] = true;\n                }\n            }\n        }\n        return count;\n    }\n    \npublic:\n    int findMaxFish(vector<vector<int>>& grid) {\n        dr = vector<int>{0, 0, 1, -1};\n        dc = vector<int>{1, -1, 0, 0};\n        int m = grid.size(), n = grid[0].size(), result = 0;\n        vector visited(m, vector<bool>(n));\n        for (int i = 0; i < m; i++) {\n            for (int j = 0; j < n; j++) {\n                if (grid[i][j] && !visited[i][j]) {\n                    result = max(result, countFishes(grid, visited, i, j));\n                }\n            }\n        }\n        return result;\n    }\n};\n```\n\n# Iterative BFS\n```\nclass Solution {\nprivate:\n    vector<int> dr, dc;\n\n    int countFishes(vector<vector<int>>& grid, vector<vector<bool>>& visited, int r, int c) {\n        int m = grid.size(), n = grid[0].size(), count = 0;\n        queue<pair<int, int>> q;\n        q.push({r, c});\n        visited[r][c] = true;\n        while (!q.empty()) {\n            r = q.front().first, c = q.front().second; q.pop();\n            count += grid[r][c];\n            for (int i = 0; i < 4; i++) {\n                int r1 = r + dr[i], c1 = c + dc[i];\n                if (0 <= r1 && r1 < m && 0 <= c1 && c1 < n && grid[r1][c1] && !visited[r1][c1]) {\n                    q.push({r1, c1});\n                    visited[r1][c1] = true;\n                }\n            }\n        }\n        return count;\n    }\n    \npublic:\n    int findMaxFish(vector<vector<int>>& grid) {\n        dr = vector<int>{0, 0, 1, -1};\n        dc = vector<int>{1, -1, 0, 0};\n        int m = grid.size(), n = grid[0].size(), result = 0;\n        vector visited(m, vector<bool>(n));\n        for (int i = 0; i < m; i++) {\n            for (int j = 0; j < n; j++) {\n                if (grid[i][j] && !visited[i][j]) {\n                    result = max(result, countFishes(grid, visited, i, j));\n                }\n            }\n        }\n        return result;\n    }\n};\n```\n\n# Union Find\n```\nclass UnionFind {\nprivate:\n    vector<int> parent, compSize, fishes;\n\npublic:\n    UnionFind(vector<vector<int>>& grid) {\n        int m = grid.size(), n = grid[0].size(), mn = m * n;\n        parent.resize(mn);\n        compSize.resize(mn, 1);\n        fishes.resize(mn);\n        iota(parent.begin(), parent.end(), 0);\n        for (int i = 0; i < m; i++) {\n            for (int j = 0; j < n; j++) {\n                fishes[n * i + j] = grid[i][j];\n            }\n        }\n    }\n\n    int getParent(int x) {\n        if (x == parent[x]) {\n            return x;\n        }\n        return parent[x] = getParent(parent[x]);\n    }\n\n    void unionSet(int x, int y) {\n        int parx = getParent(x), pary = getParent(y);\n        if (parx != pary) {\n            if (compSize[parx] < compSize[pary]) {\n                swap(parx, pary);\n            }\n            parent[pary] = parx;\n            compSize[parx] += compSize[pary];\n            fishes[parx] += fishes[pary];\n        }\n    }\n\n    int getFishes(int x) {\n        return fishes[getParent(x)];\n    }\n};\n\nclass Solution {\npublic:\n    int findMaxFish(vector<vector<int>>& grid) {\n        int m = grid.size(), n = grid[0].size(), result = 0;\n        vector<int> dr{0, 0, 1, -1}, dc{1, -1, 0, 0};\n        UnionFind dsu(grid);\n        for (int r = 0; r < m; r++) {\n            for (int c = 0; c < n; c++) {\n                if (grid[r][c]) {\n                    for (int k = 0; k < 4; k++) {\n                        int r1 = r + dr[k], c1 = c + dc[k];\n                        if (0 <= r1 && r1 < m && 0 <= c1 && c1 < n && grid[r1][c1]) {\n                            dsu.unionSet(n * r + c, n * r1 + c1);\n                        }\n                    }\n                    result = max(result, dsu.getFishes(n * r + c));\n                }\n            }\n        }\n        return result;\n    }\n};\n```\n\n\n# Complexity\n- Time complexity: $O(mn)$\n- Space complexity: $O(mn)$
['Depth-First Search', 'Breadth-First Search', 'Union Find', 'C++']