岛问题和并查集

目录
– 岛问题和并查集
– 岛问题
– 题目
– 举例
– 解法
– 代码
– 并查集
– 并查集的实现
– 初始化
– isSameSet
– merge
– findHead
– 岛问题后日谈
– 力扣官方题解中的模板

岛问题

题目

一个矩阵中只有0和1两种值，每个位置都可以和自己的上、下、左、右四个位置相连，如果有一片1连在一起，这个部分叫做一个岛
求一个矩阵中有多少个岛？

举例

001010  
111010  
100100  
000000

这个矩阵中有三个岛

解法

设计一个递归传染函数, 对于一个位置, 如果是1, 就把他改为2, 然后对其上下左右位置进行递归传染, 如果不是0, 就是base case, 什么也不做
主函数遍历每个位置, 如果是1, 就进行递归传染, 并且岛数加1计数, 否则直接跳过

代码

#include <bits/stdc++.h>
using namespace std;

class Solution
{
    void process(vector<vector<int>> &map, int i, int j, int m, int n)
    {
        if (i < 0 || i >= m || j < 0 || j >= n || map[i][j] != 1)
            return;
        else
        {
            map[i][j] = 2;
            process(map, i + 1, j, m, n);
            process(map, i - 1, j, m, n);
            process(map, i, j + 1, m, n);
            process(map, i, j - 1, m, n);
        }
    }

public:
    int NumberOfIsland(vector<vector<int>> &map)
    {
        int m = map.size();
        int n = map[0].size();
        int count = 0;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (map[i][j] == 1)
                {
                    process(map, i, j, m, n);
                    count++;
                }
            }
        }
        return count;
    }
};

int main()
{
    vector<vector<int>> map = {{0, 0, 1, 0, 1, 0},
                               {1, 1, 1, 0, 1, 0},
                               {1, 0, 0, 1, 0, 0},
                               {0, 0, 0, 0, 0, 0}};
    Solution s;
    int count = s.NumberOfIsland(map);
    cout << count << endl;
    return 0;
}

并查集

如果要求多台机器并行处理该问题, 就需要用到并查集了
即要求实现两个岛的合并, 也要求实现两个岛的查询(是否属于同一片岛)

并查集能够提供两种操作:
+ isSameSet 查询两个样本是否属于同一个集合
+ merge 将两个元素各自所在的集合合并成一个集合

并查集能实现让两个操作的时间复杂度都达到O(1)

并查集的实现

将每个样本视作链表的一环, 每个样本的代表节点就是整个链表的头节点, 链表的头节点的代表节点就是自己
若两个样本的代表结点相同, 即可说明他们属于同一个集合
实际代码实现过程中使用两个map来代替链表

初始化

定义一个小类型Element

class Element
{
    int value;

public:
    Element(int v)
    {
        value = v;
    }
};

准备三张表
map<int, Element *> elementMap;
+ key: 元素值
+ value: 元素结点

map<Element *, Element *> fatherMap;
+ key: 某个结点
+ value: key结点的父结点

map<Element *, int> sizeMap;
+ key: 某个节点
+ value: 该节点所在集合的元素个数

用于优化合并过程, 将元素个数少的集合合并到元素个数多的集合上
只有代表元素才会在这张表中有记录

map<int, Element *> elementMap;
map<Element *, Element *> fatherMap;
map<Element *, int> sizeMap;

void setUp(list<int> list)
{
    elementMap = map<int, Element *>();
    fatherMap = map<Element *, Element *>();
    sizeMap = map<Element *, int>();
    for (auto v : list)
    {
        Element *element = new Element(v);
        elementMap[v] = element;
        fatherMap[element] = element;
        sizeMap[element] = 1;
    }
}

isSameSet

循环得到头结点, 比对即可

Element *findHead(Element *element)
{
    if (element == nullptr)
        return nullptr;
    while (element != fatherMap[element])
    {
        element = fatherMap[element];
    }
    return element;
}

bool isSameSet(int a, int b)
{
    if (!elementMap.count(a) || !elementMap.count(b))
        return false; // 压根没有这些元素就别来捣乱
    return findHead(elementMap[a]) == findHead(elementMap[b]);
}

merge

先判断a和b是否在同一个集合中, 如果没有, 就在元素个数少的集合上合并到元素个数多的集合上

void merge(int a, int b)
{
    if (!elementMap.count(a) || !elementMap.count(b))
        return; // 压根没有这些元素就别来捣乱
    Element *aFather = findHead(elementMap[a]);
    Element *bFather = findHead(elementMap[b]);
    if (aFather == bFather)
        return; // 已经在一个集合里了就别来捣乱
    // 挑出数量较少的那个作为被合并的集合
    Element *big = sizeMap[aFather] >= sizeMap[bFather] ? aFather : bFather;
    Element *small = big == aFather ? bFather : aFather;
    fatherMap[small] = big; // 将小的集合的代表点的父亲设置为大的集合的代表点
    sizeMap[big] = sizeMap[aFather] + sizeMap[bFather];
    sizeMap.erase(small); // 删除小的那个集合的记录，节省空间
}

之所以可以删记录, 是因为small对应的那个节点再也不可能成为代表结点了

findHead

上面那个findHead只是一个基础版本, 可以进行扁平化优化
如果一个 “链表” 过长, 那么可能会导致findHead耗时过长
所谓的扁平化就是将一个 “链表” 的所有节点都直接连接到代表结点上, 相当于下次再找到这个节点的时候就可以直接找到代表结点了, 从而提高了效率

Element *findHead(Element *element)
{
    if (element == nullptr)
        return nullptr;
    stack<Element *> path;
    while (element != fatherMap[element])
    {
        element = fatherMap[element];
        path.push(element);
    }
    while (!path.empty())
    {
        fatherMap[path.top()] = element;
        path.pop();
    }
    return element;
}

岛问题后日谈

假想这样一个岛:

1 1 1 1 1 1 1 1 1 1 
1 0 0 0 0 0 0 0 0 1 
1 0 1 1 1 1 1 1 1 1 
1 0 1 0 0 0 0 0 0 0 
1 0 1 1 1 1 1 1 1 1 
1 0 0 0 0 0 0 0 0 1 
1 1 1 1 1 1 1 1 1 1

如果要分成左右两块交给不同的处理器处理, 假设划分情况如下

1 1 1 1 1|1 1 1 1 1 
1 0 0 0 0|0 0 0 0 1
1 0 1 1 1|1 1 1 1 1
1 0 1 0 0|0 0 0 0 0
1 0 1 1 1|1 1 1 1 1
1 0 0 0 0|0 0 0 0 1
1 1 1 1 1|1 1 1 1 1

很显然, 对于左侧有2个岛, 右侧也有2个岛, 但事实上合在一起其实只有一个岛
为了合并岛的信息, 要利用并查集
+ 在遍历岛的过程中, 附加一个标记信息, 例如左上角的1第一次被遍历到, 那么感染过程会将A标记上去, 代表ta属于集合A, 同理第二个被遍历到的中间区域左上角的1会被标记为B
+ 由于问题发生在多块划分合并时, 因此我们只需要保留边界上的信息, 在这个例子中左侧区域的右边界上的1从上至下依次被标记为A B B A(右侧同理)
+ 边界合并时即可采用并查集结构:
+ 若边界上相邻的两个格子都为岛(感染完后是2), 则直接merge即可(因为我们设计的merge方法自带isSameSet操作, 自动避免了重复合并)
+ 最终岛的数量以并查集中集合的个数为准(由于只有代表结点有记录, 因此只需要统计sizeMap中的元素个数即可)

力扣官方题解中的模板

// 并查集模板
class UnionFind {
public:
    vector<int> parent;
    vector<int> size;
    int n;
    // 当前连通分量数目
    int setCount;

public:
    UnionFind(int _n): n(_n), setCount(_n), parent(_n), size(_n, 1) {
        iota(parent.begin(), parent.end(), 0);
    }

    int findset(int x) {
        return parent[x] == x ? x : parent[x] = findset(parent[x]);
    }

    bool unite(int x, int y) {
        x = findset(x);
        y = findset(y);
        if (x == y) {
            return false;
        }
        if (size[x] < size[y]) {
            swap(x, y);
        }
        parent[y] = x;
        size[x] += size[y];
        --setCount;
        return true;
    }

    bool connected(int x, int y) {
        x = findset(x);
        y = findset(y);
        return x == y;
    }
};