C++ 8ms union-find trick solution without dfs/bfs


  • 0
    L

    While my submissions was accepted, i clicked the discuss to check how others solve this problem, and found out that this problem is a dfs/bfs search problem.
    I think i found a trick way to solve this problem, but i can not prove the correction of this solution.
    Here is my code, not to share, just want to find whether there are some special cases this solution can not solve:

    class Solution {
    public:
        int numIslands(vector<vector<char>>& grid) {
            vector<vector<int>> cntMap;
            int n = grid.size();
            int cnt = 0;
            int desc_cnt = 0;
            for (int i = 0; i < n; ++i)
            {
                int m = grid[i].size();
                vector<int> vec;
                for (int j = 0; j < m; ++j)
                {
                    if (grid[i][j] == '0')
                    {
                        vec.push_back(0);
                    }
                    else
                    {
                        int up = i > 0 ? cntMap[i - 1][j] : 0;
                        int left = j > 0 ? vec[j - 1] : 0;
                        if ((up > 0) && (left > 0))
                        {
                            if (up != left)
                            {
                                desc_cnt += 1;
                                for (int k = 0; k < j; ++k)
                                {
                                    if (vec[k] == left)
                                    {
                                        vec[k] = up;
                                    }
                                }
                            }
                            vec.push_back(up);
                        }
                        else if (up + left > 0)
                        {
                            vec.push_back(left + up);
                        }
                        else
                        {
                            cnt += 1;
                            vec.push_back(cnt);
                        }
                    }
                }
                cntMap.push_back(vec);
            }
            
            return cnt - desc_cnt;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.