A typical Union-Find one. I'm using a kinda Union-Find solution here. Some boiler-plate code - yeah I know.
class Solution {
unordered_set<int> hs; // start from 1
int max_k;
public:
void dfs(vector<vector<int>> &mt, int x, int y, int f)
{
int n = mt.size(), m = mt[].size();
mt[y][x] = f;
if(x > && mt[y][x - ] != f && mt[y][x - ] != ) // left
{
mt[y][x - ] = f;
dfs(mt, x - , y, f);
}
if(x < m - && mt[y][x + ] != f && mt[y][x + ] != ) // right
{
mt[y][x + ] = f;
dfs(mt, x + , y, f);
}
if(y > && mt[y - ][x] != f && mt[y - ][x] != ) // up
{
mt[y - ][x] = f;
dfs(mt, x, y - , f);
}
if(y < n - && mt[y + ][x] != f && mt[y + ][x] != ) // down
{
mt[y + ][x] = f;
dfs(mt, x, y + , f);
}
}
void update(vector<vector<int>> &mt, Point &p)
{
int n = mt.size(), m = mt[].size();
int minf = INT_MAX;
vector<Point> to_union;
if(p.x > ) // left
{
if(mt[p.y][p.x - ] != )
{
minf = min(minf, mt[p.y][p.x - ]);
to_union.push_back(Point(p.x - , p.y));
}
}
if(p.x < m - ) // right
{
if(mt[p.y][p.x + ] != )
{
minf = min(minf, mt[p.y][p.x + ]);
to_union.push_back(Point(p.x + , p.y));
}
}
if(p.y > ) // update
{
if(mt[p.y - ][p.x] != )
{
minf = min(minf, mt[p.y - ][p.x]);
to_union.push_back(Point(p.x, p.y - ));
}
}
if(p.y < n - ) // down
{
if(mt[p.y + ][p.x] != )
{
minf = min(minf, mt[p.y + ][p.x]);
to_union.push_back(Point(p.x, p.y + ));
}
}
////
if(minf == INT_MAX)
{
int np = max_k ++;
mt[p.y][p.x] = np;
hs.insert(np);
}
else
{
mt[p.y][p.x] = minf;
for(auto &tp:to_union)
{
if(mt[tp.y][tp.x] != && mt[tp.y][tp.x] != minf)
{
int old = mt[tp.y][tp.x];
dfs(mt, tp.x, tp.y, minf);
hs.erase(old);
}
}
}
}
/**
* @param n an integer
* @param m an integer
* @param operators an array of point
* @return an integer array
*/
vector<int> numIslands2(int n, int m, vector<Point>& operators){
vector<vector<int>> mt(m, vector<int>(n));
max_k = ;
vector<int> ret;
for(auto &p : operators)
{
update(mt, p);
ret.push_back(hs.size());
}
return ret;
}
};