# Sharing my C++ solution

• ``````class Solution {
private:
vector<int> graph;

int find(int x)
{
if(x==graph[x])
return x;
else
return find(graph[x]);
}

public:
vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
graph.resize(m*n);
int i, j;
for(i=0; i<m; i++)
for(j=0; j<n; j++)
graph[i*n+j] = i*n+j;

vector<int> result;
int count=0;
vector<vector<bool>> visited(m, vector<bool>(n, false));
int direction[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
int x, y, nextX, nextY, current, next;
for(i=0; i<positions.size(); i++)
{
x = positions[i].first;
y = positions[i].second;
if(visited[x][y])
continue;

visited[x][y] = true;
count++;
current = x*n+y;
for(j=0; j<4; j++)
{
nextX = x + direction[j][0];
nextY = y + direction[j][1];
next = nextX*n+nextY;
if(nextX>=0 && nextX<m && nextY>=0 && nextY<n && visited[nextX][nextY] && find(next) != current)
{
graph[find(next)] = current;
count--;
}
}

result.push_back(count);
}

return result;
}
};``````

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