Leetcode 305 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;
    }
};