# Leetcode 305 Solution

https://leetcode.com/problems/number-of-islands-ii

## Solution

``````class FindAndUnionSet
{
int* parent;
public:
FindAndUnionSet(int size)
{
parent = new int[size];
for (int i = 0; i < size; i++)
parent[i] = i;
}

int Find(int i)
{
return parent[i] == i ? i : parent[i] = Find(parent[i]);
}

void Union(int i, int j)
{
int pi = Find(i);
int pj = Find(j);
parent[pj] = pi;
}
};

class Solution {
public:
vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
FindAndUnionSet s(m * n);

vector<int> res;
int last_number = 0;
unordered_set<int> islands;
for (auto pos : positions)
{
int i = pos.first;
int j = pos.second;

unordered_map<int, pair<int, int>> neighbors;
if (i > 0 && islands.find((i - 1) * n + j) != islands.end())
neighbors[s.Find((i - 1) * n + j)] = make_pair(i - 1, j);

if (i < m - 1 && islands.find((i + 1) * n + j) != islands.end())
neighbors[s.Find((i + 1) * n + j)] = make_pair(i + 1, j);

if (j > 0 && islands.find(i * n + j - 1) != islands.end())
neighbors[s.Find(i * n + j - 1)] = make_pair(i, j - 1);

if (j < n - 1 && islands.find(i * n + j + 1) != islands.end())
neighbors[s.Find(i * n + j + 1)] = make_pair(i, j + 1);

if (neighbors.size() == 0)
last_number++;
else
{
last_number -= neighbors.size() - 1;
for (auto nei : neighbors)
s.Union(i * n + j, nei.second.first * n + nei.second.second);
}

islands.insert(i * n + j);
res.push_back(last_number);
}

return res;
}
};
``````