union find

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

#include <vector>
#include <unordered_map>
#include <algorithm>
#include <iostream>

using namespace std;


class Solution
{
    public:
        int find(int x)
        {
            if (parent[x] == x)
                return x;
            parent[x] = find(parent[x]);
            return parent[x];
        }

        void Union(int x, int y)
        {
            int px = find(x), py = find(y);
            if (px != py)
            {
                if (size[px] < size[py])
                {
                    parent[px] = py;
                    size[py] += size[px];
                }
                else
                {
                    parent[py] = px;
                    size[px] += size[py];
                }
            }
        }

        int longestConsecutive(vector<int> &input)
        {
            int len = input.size();
            if (len < 2)
                return len;
            size = vector<int>(len, 1);
            for (int i = 0; i < len; ++i)
                parent.push_back(i);
            unordered_map<int, int> record;
            for (int i = 0; i < len; ++i)
            {
                if (record.find(input[i]) != record.end())
                    continue;
                record[input[i]] = i;
                if (record.find(input[i] - 1) != record.end())
                    Union(i, record[input[i] - 1]);
                if (record.find(input[i] + 1) != record.end())
                    Union(i, record[input[i] + 1]);
            }
            return *max_element(size.begin(), size.end());
        }
    private:
        vector<int> parent;
        vector<int> size;
};

int main()
{
    vector<int> input({100, 4, 200, 1, 3, 2});
    Solution s;
    cout << s.longestConsecutive(input);
}

给一个01矩>阵，求不同的岛屿的个数。0代表海，1代表岛，如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。

样例

在矩阵：

[
[1, 1, 0, 0, 0],
[0, 1, 0, 0, 1],
[0, 0, 0, 1, 1],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 1]
]
中有 3 个岛.

1. 并查集

#include <iostream>
#include <vector>

using namespace std;

class Solution
{
    public:
        int find(int x)
        {
            if (parent[x] == x)
                return x;
            parent[x] = find(parent[x]);
            return parent[x];
        }

        bool isConnected(int x, int y)
        {
            return find(x) == find(y);
        }

        void Union(int x, int y)
        {
            int px = find(x), py = find(y);
            if (px != py)
            {
                if (size[px] < size[py])
                {
                    parent[px] = py;
                    size[py] += size[px];
                }
                else
                {
                    parent[py] = px;
                    size[px] += size[py];
                }
            }
        }

        int numIslands(vector<vector<int> > &matrix)
        {
            if (matrix.empty())
            {
                return 0;
            }
            int rows = matrix.size(), cols = matrix[0].size();
            parent.resize(rows * cols);
            size.resize(rows * cols);
            int count = 0;
            for (int i = 0; i < rows; ++i)
                for (int j = 0; j < cols; ++j)
                {
                    if (matrix[i][j] == 1)
                    {
                        count++;
                        parent[cols * i + j] = cols * i + j;
                    }
                }

            vector<vector<int> > directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
            for (int i = 0; i < rows; ++i)
                for (int j = 0; j < cols; ++j)
                    if (matrix[i][j] == 1)
                        for (auto dir : directions)
                        {
                            int x = i + dir[0], y = j + dir[1];
                            if (x < 0 || y < 0 || x >= rows || y >= cols || matrix[x][y] != 1)
                                continue;
                            if (!isConnected(i * cols + j, x * cols + y))
                            {
                                Union(i * cols + j, x * cols + y);
                                count--;
                            }

                        }
            return count;
        }
    private:
        vector<int> parent;
        vector<int> size;
};

int main()
{
    vector<vector<int> > matrix({
            {1, 1, 0, 0, 0},
            {0, 1, 0, 0, 1},
            {0, 0, 0, 1, 1},
            {0, 0, 0, 0, 0},
            {0, 0, 0, 0, 1}
            });
    if (matrix.empty())
        return 0;
    int rst = 0;
    Solution s;
    rst = s.numIslands(matrix);
    return rst;

}

1. 广度优先或深度优先

#include <iostream>
#include <vector>
#include <stack>
#include <utility>

using namespace std;

void dfs(vector<vector<int> >& matrix, int i, int j)
{
    if (i < 0 || j < 0 || i >= matrix.size() || j >= matrix[0].size())
        return;

    if(matrix[i][j] == 1)
    {
        matrix[i][j] = 0;
        dfs(matrix, i - 1, j);
        dfs(matrix, i + 1, j);
        dfs(matrix, i, j - 1);
        dfs(matrix, i, j + 1);
    }
}

void bfs(vector<vector<int> > &matrix, int i, int j)
{
    if (i < 0 || j < 0 || i >= matrix.size() || j >= matrix[0].size())
        return;

    if (matrix[i][j] == 1)
    {
        stack<pair<int, int> > s;
        s.push(make_pair(i, j));
        while(!s.empty())
        {
            pair<int, int> idxy = s.top();
            s.pop();
            int x = idxy.first, y = idxy.second;
            matrix[x][y] = 0;
            if (x > 0 && matrix[x - 1][y] == 1)
                s.push(make_pair(x - 1, y));
            if (x < matrix.size() - 1 && matrix[x + 1][y] == 1)
                s.push(make_pair(x + 1, y));
            if (y > 0 && matrix[x][y - 1] == 1)
                s.push(make_pair(x, y - 1));
            if (y < matrix[0].size() - 1 && matrix[x][y + 1] == 1)
                s.push(make_pair(x, y + 1));
        }
    }
}

int main()
{
    vector<vector<int> > matrix({
            {1, 1, 0, 0, 0},
            {0, 1, 0, 0, 1},
            {0, 0, 0, 1, 1},
            {0, 0, 0, 0, 0},
            {0, 0, 0, 0, 1}
            });
    if (matrix.empty())
        return 0;
    int rst = 0;
    for (int i = 0; i < matrix.size(); ++i)
        for (int j = 0; j < matrix[0].size(); ++j)
        {
            if (matrix[i][j] == 1)
            {
                ++rst;
                bfs(matrix, i, j);
                // dfs(matrix, i, j);
            }

        }
    return rst;

}