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

• 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;
}
};
``````

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