并查集主要用来解决动态连通性问题。
连通性问题：
LC200 Number of Islands
LC305 Number of Islands II
LC547 Friend Circles
LC130 Surrounded Regions

实现并查集

Weighted Quick-Union with Path Compression

建议参考：Algorithm 4th edition, Union-Find

定义：

一个节点i的父节点为tree[i]
一个节点i所在的树的根节点j为父节点为自己的祖先节点，即tree[j] == j。

初始化：

所有的节点i的父节点为其自己，即初始化时赋值tree[i] = i
因此，以所有节点i为根节点的集合（树）的初始化为1

find()的实现思路：

两个节点在一个集合（树）中，当且仅当他们的集合（树）的根节点是相同的。
Path compression: 每次在找到一个节点所在集合的根节点的过程中，将从根节点到该节点路径上的所有节点的父节点都设置为根节点。
union() / connect()的实现思路：
要将两个节点合并，就是将他们所在的集合（树）合并。因此我们可以把其中一个集合（树）的根节点的父节点设置为另一个集合（树）的根节点。
Weighted Quick-Union: 我们记录以每一个节点为根节点的树的大小。我们总是将含有元素较少的集合（树）的根节点的父节点改为含有较多元素的集合（树）的根节点。

实现1

class disjoint_set
{
private:
    vector<size_t> tree;
    vector<size_t> size;
public:
    disjoint_set(size_t sz)
    : tree(sz)
    , size(sz, 1)
    {
        iota(tree.begin(), tree.end(), 0);
    }
    size_t find(size_t idx)
    {
        vector<size_t> ids{};
        while(idx != tree[idx])
        {
            ids.push_back(idx);
            idx = tree[idx];
        }
        for(auto x : ids) tree[x] = idx;
        return idx;
    }

    bool connect(size_t idx1, size_t idx2)
    {
        auto rt1 = find(idx1);
        auto rt2 = find(idx2);

        if(rt1 == rt2) 
            return false;

        if(size[rt1] < size[rt2]) 
            swap(rt1, rt2);
        
        tree[rt2] = rt1;
        rt1 += size[rt2];

        return true;
        
    }

    bool is_single_set()
    {
        return adjacent_find(tree.begin(), tree.end(), [this](auto lhs, auto rhs){return find(lhs) != find(rhs);}) == tree.end();
    }
};

实现2

template<typename T>
class UnionFind
{
public:
explicit UnionFind(T num):
        tree(num),
        size(num, 1)
{
    iota(tree.begin(), tree.end(), 0);
}

T find(T index)
{
    if(tree[index] != index)
        tree[index] = find(tree[index]);
    return tree[index];
}

bool connect(T idx1, T idx2)
{
    T root1 = find(idx1);
    T root2 = find(idx2);

    if(root1 != root2)
    {
        if(size[root1] < size[root2])
        {
            tree[root1] = root2;
            size[root2] += size[root1];
        }
        else
        {
            tree[root2] = root1;
            size[root1] += size[root2];
        }

        return true;
    }

    return false;
}
private:
vector<T> tree;
vector<T> size;
};

连通性问题

岛屿数量

LC200, Number of Islands, LC305, Number of Islands II

其中第一题LC200, Number of Islands不是动态的连通性问题，因此也可以用DFS来统计深度优先森林中树的个数或用BFS来遍历。

思路1 并查集：

将坐标[i][j]转换成唯一对应的index = i * numCols + j，作为并查集的index
初始化一个同样大小的并查集和一个计数器count=0。
遍历矩阵，每次遇到1的时候
- 增加计数器++count
- 尝试合并这个元素[i][j]和他上方的元素[i - 1][j]以及他左边的元素[i][j - 1]
- 如果这个元素和他上方的元素以及他左边的元素不在一个set里，那么减少计数器--count。因为：
  - 如果这个元素和其中一个元素连通了，没有增加岛屿的数量。
  - 如果这个元素和两个都成功连通了，那么这个元素就将矩阵里原来的两个岛接在了一起。那么岛屿数量会-1。(++count, --count, --count)
返回计数器的值

2020.6.17 code

class disjoint_set
{
public:
    explicit disjoint_set(size_t size)
    :m_tree(size)
    ,m_size(size, 1)
    {
        iota(m_tree.begin(),  m_tree.end(), 0);
    }

    auto root(size_t index)
    {
        std::vector<size_t> indices{};
        while(m_tree[index] != index)
        {
            indices.push_back(index);
            index = m_tree[index];
        }
        // m_tree[index] == index, we find the root
        // then we do path compression
        for(auto idx : indices)
        {
            m_tree[idx] = index;
        }

        return index;
    }

    auto connect(size_t i, size_t j)
    {
        auto i_root = root(i);
        auto j_root = root(j);

        // fail to connect if they are in the same tree
        if(i_root == j_root)
        {
            return false;
        }

        // check which tree that i or j belongs to has greater size
        if(m_size[i_root] < m_size[j_root])
        {
            swap(i_root, j_root);
        }

        m_tree[j_root] = i_root;
        m_size[i_root] += m_size[j_root];

        return true;
    }
private:
    vector<size_t> m_tree;
    vector<size_t> m_size;
};

class Solution {
private:
    inline constexpr static const char LAND = '1';
    inline constexpr static const char WATER = '0';
public:
    int numIslands(vector<vector<char>>& grid) {

        if(grid.empty())
        {
            return 0;
        }

        auto uf = disjoint_set{grid.size() * grid.front().size()};

        auto to_index = [&](size_t i, size_t j)
        {
            return i * grid.front().size() + j;
        };
        
        auto is_valid_land = [&](size_t i, size_t j)
        {
            return 
                i >= 0 && j >= 0 
            &&  i < grid.size() && j < grid.front().size() 
            &&  grid[i][j] == LAND;
        };

        auto res = size_t{};

        for(auto i = size_t{}; i < grid.size(); ++i)
        {
            for(auto j = size_t{}; j < grid.front().size(); ++j)
            {
                if(grid[i][j] == LAND)
                {
                    ++res;
                    if(is_valid_land(i - 1, j))
                    {
                        res -= uf.connect(to_index(i, j), to_index(i - 1, j));
                    }

                    if(is_valid_land(i, j - 1))
                    {
                        res -= uf.connect(to_index(i, j), to_index(i, j - 1));
                    }
                }
            }
        }

        return res;
    }
};

code

using namespace std;
template<typename T>
class UnionFind
{
public:
explicit UnionFind(T num):
        tree(num),
        size(num, 1)
{
    iota(tree.begin(), tree.end(), 0);
}

T find(T index)
{
    if(tree[index] != index)
        tree[index] = find(tree[index]);
    return tree[index];
}

bool connect(T idx1, T idx2)
{
    T root1 = find(idx1);
    T root2 = find(idx2);

    if(root1 != root2)
    {
        if(size[root1] < size[root2])
        {
            tree[root1] = root2;
            size[root2] += size[root1];
        }
        else
        {
            tree[root2] = root1;
            size[root1] += size[root2];
        }

        return true;
    }

    return false;
}
private:
vector<T> tree;
vector<T> size;
};

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty() || grid.front().empty()) return 0;

        // assume it's ok to use int
        nr = static_cast<int>(grid.size());
        nc = static_cast<int>(grid.front().size());

        // initialize

        count = 0;
        set = new UnionFind<int>{nr * nc};

        for(int i = 0; i < nr; ++i)
        {
            for (int j = 0; j < nc; ++j)
            {
                if (grid[i][j] == ISLAND)
                {
                    ++count;
                    if (i != 0 && grid[i - 1][j] == ISLAND) 
                        connect(toIndex(i, j), toIndex(i - 1, j));
                    if (j != 0 && grid[i][j - 1] == ISLAND)
                        connect(toIndex(i, j), toIndex(i, j - 1));         
                }
            }
        }

        delete set;
        return count;
    }
private:
    constexpr static char ISLAND = '1';
    int nr;
    int nc;
    int count;
    UnionFind<int>* set;

    void connect(int idx1, int idx2)
    {
        if(set->connect(idx1, idx2))
        {
            --count;
        }
    }

    int toIndex(int i, int j)
    {
        return i * nc + j;
    }
};

思路2: BFS

遍历所有节点，每当遇到1的节点时，计数器+1。之后从该节点开始进行BFS。BFS过程中，把所有遇到的节点都置0。

注意：在BFS时，要在第一次遇到一个节点时就将该节点置'0'，否则将会导致重复遍历。

                            duplicate
                            +
                            |
                            v
+-----+      +-----+       ++----+
|1|1| |      |1|0| |       |1|0| |
+-----+      +-----+       +-----+
|1|X|1| +--> |1|0|1|  +--> |0|0|1|
+-----+      +-----+       +-----+
| |1| |      | |1| |       | |1| |
+-----+      +-----+       +-----+

从'X'的位置开始进行BFS，按照“上左下右”的顺序将'X'周围的四个LAND放入BFS队列中而不清零。之后从队列中取出队列头（即'X'上面的'1'），将该队列头清零后，把其左边的'1'放入队列。之后再取出队列头（即'X'右边的'1'）。注意此时在便利该队列头周围的节点时，会重复地将左上角的'1'再次放入队列。

code

class Solution {
public:
    constexpr static const char LAND  = '1';
    constexpr static const char WATER = '0';

    struct point
    {
        size_t i;
        size_t j;
    };

    int numIslands(vector<vector<char>>& grid) {
        auto is_valid_land = [&](point pt)
        {
            return pt.i >=0 && pt.j >=0
            &&     pt.i < grid.size() && pt.j < grid.front().size()
            &&     grid[pt.i][pt.j] == LAND;
        };

        auto connected_poses = [&](point pt)
        {
            return array
            {
                point{pt.i + 1, pt.j},
                point{pt.i - 1, pt.j},
                point{pt.i, pt.j - 1},
                point{pt.i, pt.j + 1}
            };
        };

        auto set_water = [&](point pt)
        {
            grid[pt.i][pt.j] = WATER;
        };

        auto bfs = [&](point pt)
        {
            auto bfs_queue = queue<point>{};
            set_water(pt);
            bfs_queue.push(pt);

            while(!bfs_queue.empty())
            {
                for(auto c_pt : connected_poses( bfs_queue.front() ))
                {
                    if(is_valid_land(c_pt))
                    {
                        set_water(c_pt);
                        bfs_queue.push(c_pt);
                    }
                }

                bfs_queue.pop();
            }
        };

        auto res = size_t{};

        for(auto i = size_t{}; i < grid.size(); ++i)
        {
            for(auto j = size_t{}; j < grid.front().size(); ++j)
            {
                if(grid[i][j] == LAND)
                {
                    ++res;
                    bfs(point{i, j});
                }
            }
        }

        return res;
    }
};

朋友圈

LC547 Friend Circles
同上两题。这个题可以利用无向图邻接矩阵的对称性，不需要遍历矩阵所有部分。只需要遍历右上角即可。

在并查集里统计不交集的个数。开始时不交集的个数等于节点的个数。每次成功合并两个不交集，都会使得不交集的个数减1。

2020.6.17 code

class disjoint_set
{
public:
    explicit disjoint_set(size_t size)
    :m_tree(size)
    ,m_size(size, 1)
    ,m_set_num{size}
    {
        iota(m_tree.begin(),  m_tree.end(), 0);
    }

    auto root(size_t index)
    {
        std::vector<size_t> indices{};
        while(m_tree[index] != index)
        {
            indices.push_back(index);
            index = m_tree[index];
        }
        // m_tree[index] == index, we find the root
        // then we do path compression
        for(auto idx : indices)
        {
            m_tree[idx] = index;
        }

        return index;
    }

    auto set_num()
    {
        return m_set_num;
    }

    auto connect(size_t i, size_t j)
    {
        auto i_root = root(i);
        auto j_root = root(j);

        // fail to connect if they are in the same tree
        if(i_root == j_root)
        {
            return false;
        }

        // check which tree that i or j belongs to has greater size
        if(m_size[i_root] < m_size[j_root])
        {
            swap(i_root, j_root);
        }

        m_tree[j_root] = i_root;
        m_size[i_root] += m_size[j_root];
        --m_set_num;
        return true;
    }
private:
    vector<size_t> m_tree;
    vector<size_t> m_size;
    size_t m_set_num;
};

class Solution {
public:
    int findCircleNum(vector<vector<int>>& M) 
    {
        auto uf = disjoint_set{M.size()};
        for(auto i = size_t{}; i < M.size(); ++i)
        {
            for(auto j = size_t{i} + 1; j < M.size(); ++j)
            {
                if(M[i][j] == 1)
                {
                    uf.connect(i, j);
                }
            }
        }

        return uf.set_num();
    }
};

code

class ufset
{
private:
    vector<int> tree;
    vector<int> size;
public:
    ufset(int num)
    :tree(num)
    ,size(num, 1)
    {
        iota(tree.begin(), tree.end(), 0);
    }
    int find(int idx)
    {
        if(tree[idx] != idx)
        {
            tree[idx] = find(tree[idx]);
        }

        return tree[idx];
    }

    bool connect(int idx1, int idx2)
    {
        int rt1 = find(idx1);
        int rt2 = find(idx2);

        if (rt1 == rt2) return false;

        if (size[rt1] < size[rt2])
        {
            tree[rt1] = rt2;
            size[rt2] += size[rt1]; 
        }
        else // size[rt1] >= size[rt2]
        {
            tree[rt2] = rt1;
            size[rt1] += size[rt2];
        }

        return true;
    }
};

class Solution {
public:
    int findCircleNum(vector<vector<int>>& M) {
        if(M.empty() || M.front().empty()) return 0;

        // initialize
        size_t N = M.size();
        int count = N;
        ufset uf(N);

        for (size_t i = 0; i < N; ++i)
            for (size_t j = i + 1; j < N; ++j)
                if (1 == M[i][j] && uf.connect(i, j))
                   --count;
        return count;
    }
};

账户合并

LC721, 账户合并

按列表中的元素个数，建立一个相同大小的并查集。列表中元素的索引，即是其在并查集中的索引。
建立一个由【邮箱】到【索引】的unordered_map : mail_index_map。
遍历所有的邮箱：
- 如果在mail_index_map中没有找到对应的【索引】，则建立对应关系。
- 如果在mail_index_map中找到了对应的【索引】，则出现了重复的邮箱。那么这个【邮箱】所对应的索引，应该和原来的【索引】合并。在并查集中connect对应的【索引】
建立一个由【索引】到【邮箱集合】(set)的unordered_map。
遍历所有的【索引】，在并查集中找到他们的root。将该【索引】下的所有邮箱放入root对应的【邮箱集合】中。
遍历由【索引】到【邮箱集合】的map，生成结果。

code

class disjoint_set
{
public:
    explicit disjoint_set(size_t size)
    :m_tree(size)
    ,m_size(size, 1)
    ,m_set_num{size}
    {
        iota(m_tree.begin(),  m_tree.end(), 0);
    }

    auto root(size_t index)
    {
        std::vector<size_t> indices{};
        while(m_tree[index] != index)
        {
            indices.push_back(index);
            index = m_tree[index];
        }
        // m_tree[index] == index, we find the root
        // then we do path compression
        for(auto idx : indices)
        {
            m_tree[idx] = index;
        }

        return index;
    }

    auto set_num()
    {
        return m_set_num;
    }

    auto connect(size_t i, size_t j)
    {
        auto i_root = root(i);
        auto j_root = root(j);

        // fail to connect if they are in the same tree
        if(i_root == j_root)
        {
            return false;
        }

        // check which tree that i or j belongs to has greater size
        if(m_size[i_root] < m_size[j_root])
        {
            swap(i_root, j_root);
        }

        m_tree[j_root] = i_root;
        m_size[i_root] += m_size[j_root];
        --m_set_num;
        return true;
    }

    vector<size_t> m_tree;
    vector<size_t> m_size;
    size_t m_set_num;
};

class Solution {
public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        auto mail_index_map = unordered_map<string_view, size_t>{};
        auto index_uf = disjoint_set{accounts.size()};

        for(auto i = size_t{}; i < accounts.size(); ++i)
        {
            for(auto it = ++accounts[i].begin(); it != accounts[i].end(); ++it)
            {
                auto mail_view = string_view{it->data(), it->size()};
                if(auto it = mail_index_map.find(mail_view);
                it == mail_index_map.end())
                {
                    mail_index_map[mail_view] = i;
                }
                else
                {
                    index_uf.connect(i, it->second);
                }
            }
        }

        auto index_mail_map = unordered_map<size_t, set<string_view>>{};

        for(auto i = size_t{}; i < accounts.size(); ++i)
        {
            auto root = index_uf.root(i);
            index_mail_map[root].insert(++accounts[i].begin(), accounts[i].end());
        }

        auto res = vector<vector<string>>{};

        transform(index_mail_map.begin(), index_mail_map.end(), back_inserter(res), [&](const auto& pair)
        {
            auto vec = vector<string>{};
            vec.push_back(accounts[pair.first][0]);
            for(auto mail : pair.second)
            {
                vec.emplace_back(mail);
            }
            return vec;
        });

        return res;
    }
};

被围绕的区域

LC130, Surrounded Regions

这个题更适合用DFS，而不是并查集。DFS不需要遍历所有的元素，只生成从边界上的'O'出发的深度优先森林即可。
并查集的思路：

- 设置哨兵元素`edgeGuard`
- 按从上到下、从左到右的顺序遍历矩阵每一个元素：
    - 如果是边界上的元素，那么把他和`edgeGurad`合并
    - 和左边元素、上边元素合并。
- 寻找所有O的root，不是`edgeGuard`的就改成`X`

2020.6.17 code

class disjoint_set
{
public:
    explicit disjoint_set(size_t size)
    :m_tree(size, 0)
    ,m_size(size, 1)
    {
        iota(m_tree.begin(), m_tree.end(), 0);
    }

    auto root(size_t idx) -> size_t
    {
        auto indices = vector<size_t>{};
        while(m_tree[idx] != idx)
        {
            indices.push_back(idx);
            idx = m_tree[idx];
        }

        for(auto index : indices)
        {
            m_tree[index] = idx;
        }

        return idx;
    }

    auto connect(size_t i, size_t j) -> bool
    {
        auto root_i = root(i);
        auto root_j = root(j);

        if(root_i == root_j)
        {
            return false;
        }

        if(m_size[root_i] < m_size[root_j])
        {
            swap(root_i, root_j);
        }

        m_tree[root_j] = root_i;
        m_size[root_i] += m_size[root_j];

        return true;
    }
private:
    vector<size_t> m_tree;
    vector<size_t> m_size;
};

class Solution {
public:
    void solve(vector<vector<char>>& board) 
    {
        if(board.empty() || board.front().empty())
        {
            return;
        }
        
        struct point
        {
            size_t x;
            size_t y;

            decltype(auto) adjacent()
            {
                return array
                {
                    point{x + 1, y},
                    point{x - 1, y},
                    point{x, y + 1},
                    point{x, y - 1}
                };
            }
        };
        
        auto is_on_boundary = [&](point pt)
        {
            return pt.x == 0 || pt.y == 0 
            || pt.x == board.size() - 1 || pt.y == board.front().size() - 1;
        };

        auto is_valid_point = [&](point pt)
        {
            return pt.x >= 0 && pt.y >= 0 
            && pt.x < board.size() && pt.y < board.front().size();
        };

        auto to_index = [&](point pt) -> size_t
        {
            return pt.x * board.front().size() + pt.y;
        };

        const auto guard_index = board.size() * board.front().size();
        auto uf = disjoint_set{guard_index + 1};

        for(auto i = size_t{}; i < board.size(); ++i)
        {
            for(auto j = size_t{}; j < board.front().size(); ++j)
            {
                if(board[i][j] == 'O')
                {
                    auto p = point{i, j};

                    if(is_on_boundary(p))
                    {
                        uf.connect(to_index(p), guard_index);
                    }

                    for(auto pt : p.adjacent())
                    {
                        if(is_valid_point(pt) && board[pt.x][pt.y] == 'O')
                        {
                            uf.connect(to_index(pt), to_index(p));
                        }
                    }
                }
            }
        }

        for(auto i = size_t{}; i < board.size(); ++i)
        {
            for(auto j = size_t{}; j < board.front().size(); ++j)
            {
                if(board[i][j] == 'O' 
                && uf.root(to_index(point{i, j})) != uf.root(guard_index))
                {
                    board[i][j] = 'X';
                }
            }
        }
    }
};

code

class ufs
{
public:
    ufs(size_t num);
    size_t find(size_t idx);
    bool connect(size_t idx1, size_t idx2);
private:
    vector<size_t> tree;
    vector<size_t> size;
};

ufs::ufs(size_t num)
        :tree(num)
        ,size(num, 1)
{
    iota(tree.begin(), tree.end(), 0);
}

size_t ufs::find(size_t idx)
{
    if(tree[idx] != idx) tree[idx] = find(tree[idx]);
    return tree[idx];
}

bool ufs::connect(size_t idx1, size_t idx2)
{
    size_t rt1 = find(idx1);
    size_t rt2 = find(idx2);

    if (rt1 == rt2)
        return false;

    if (size[rt1] < size[rt2])
    {
        tree[rt1] = rt2;
        size[rt2] += size[rt1];
    }
    else //size[rt1] >= size[rt2]
    {
        tree[rt2] = rt1;
        size[rt1] += size[rt2];
    }

    return true;
}

class Solution {
private:
    constexpr static char LETTER_O = 'O';
    size_t numRow;
    size_t numCol;
    size_t guard;
    ufs* uf;
    inline size_t toIndex(size_t x, size_t y);
    inline void connect(size_t x1, size_t y1, size_t x2, size_t y2);
    void connectGuard(size_t x, size_t y);

public:
    void solve(vector<vector<char>>& board);
};

void Solution::connect(size_t x1, size_t y1, size_t x2, size_t y2)
{
    uf->connect(toIndex(x1, y1), toIndex(x2, y2));
}

void Solution::connectGuard(size_t x, size_t y)
{
    uf->connect(guard, toIndex(x, y));
}

size_t Solution::toIndex(size_t x, size_t y)
{
    return x * numCol + y;
}

void Solution::solve(vector<vector<char>>& board)
{
    if (board.empty() || board.front().empty()) return;
    numRow = board.size();
    numCol = board.front().size();

    // initialize ufs
    guard = numRow * numCol;
    uf = new ufs{guard + 1};

    for(size_t i = 0; i < numRow; ++i)
        for(size_t j = 0; j < numCol; ++j)
            if (board[i][j] == LETTER_O)
            {
                // if it is on the edge
                if (i == 0 || j == 0 || i == numRow - 1 || j == numCol - 1)
                {
                    //connect it with the gurad
                    connectGuard(i, j);
                }
                if (i != 0 && LETTER_O == board[i - 1][j])
                    connect(i, j, i - 1, j);
                if (j != 0 && LETTER_O == board[i][j - 1])
                    connect(i, j, i, j - 1);
            }
    for(size_t i = 0; i < numRow; ++i)
        for(size_t j = 0; j < numCol; ++j)
            if (uf->find(toIndex(i,j)) != uf->find(guard))
                board[i][j] = 'X';

    delete uf;
}

句子相似性

LC737 句子相似性II

并查集的简单应用。需要注意的：

句子中会有下面相似单词中没有的单词。
如果出现没有的单词，也不可以马上认为句子不相似。因为如果这两个没有的单词可能是完全相同的。

code

class disjoint_set
{
public:
    explicit disjoint_set(size_t size)
    :m_tree(size, 0)
    ,m_size(size, 1)
    {
        iota(m_tree.begin(), m_tree.end(), 0);
    }

    auto root(size_t idx) -> size_t
    {
        auto indices = vector<size_t>{};
        while(m_tree[idx] != idx)
        {
            indices.push_back(idx);
            idx = m_tree[idx];
        }

        for(auto index : indices)
        {
            m_tree[index] = idx;
        }

        return idx;
    }

    auto connect(size_t i, size_t j) -> bool
    {
        auto root_i = root(i);
        auto root_j = root(j);

        if(root_i == root_j)
        {
            return false;
        }

        if(m_size[root_i] < m_size[root_j])
        {
            swap(root_i, root_j);
        }

        m_tree[root_j] = root_i;
        m_size[root_i] += m_size[root_j];

        return true;
    }
private:
    vector<size_t> m_tree;
    vector<size_t> m_size;
};

class Solution {
public:
    bool areSentencesSimilarTwo(vector<string>& words1, vector<string>& words2, vector<vector<string>>& pairs) 
    {
        if(words1.size() != words2.size())
        {
            return false;
        }

        auto word_index_map = unordered_map<string_view, size_t>{};
        const auto word_num = [&]
        {
            auto index = size_t{};
            for(const auto& pair : pairs)
            {
                for(string_view word : pair)
                {
                    if(auto it = word_index_map.find(word);
                        it == word_index_map.end())
                    {
                        word_index_map[word] = index++;
                    }
                }
            }
            return word_index_map.size();
        }();

        auto uf = disjoint_set{word_num};

        for(const auto& pair : pairs)
        {
            uf.connect(word_index_map[pair[0]],word_index_map[pair[1]]);
        }

        return mismatch(words1.begin(), words1.end(), words2.begin(), 
        [&](string_view word1, string_view word2)
        {
            if(word1 == word2)
            {
                return true;
            }
            
            if(word_index_map.find(word1) == word_index_map.end() || 
               word_index_map.find(word2) == word_index_map.end())
            {
                return false;
            }

            return uf.root(word_index_map[word1]) == uf.root(word_index_map[word2]);
        }) == make_pair(words1.end(), words2.end());

    }
};

动态连通性

LC305, Number of Islands II

动态连通性问题，同上题，维护一个并查集即可。需要注意的问题是：测试用例中有positions中有重复的坐标，需要判断并跳过。

2020.6.17 code

class disjoint_set
{
public:
    explicit disjoint_set(size_t size)
    :m_tree(size)
    ,m_size(size, 1)
    {
        iota(m_tree.begin(),  m_tree.end(), 0);
    }

    auto root(size_t index)
    {
        std::vector<size_t> indices{};
        while(m_tree[index] != index)
        {
            indices.push_back(index);
            index = m_tree[index];
        }
        // m_tree[index] == index, we find the root
        // then we do path compression
        for(auto idx : indices)
        {
            m_tree[idx] = index;
        }

        return index;
    }

    auto connect(size_t i, size_t j)
    {
        auto i_root = root(i);
        auto j_root = root(j);

        // fail to connect if they are in the same tree
        if(i_root == j_root)
        {
            return false;
        }

        // check which tree that i or j belongs to has greater size
        if(m_size[i_root] < m_size[j_root])
        {
            swap(i_root, j_root);
        }

        m_tree[j_root] = i_root;
        m_size[i_root] += m_size[j_root];

        return true;
    }
private:
    vector<size_t> m_tree;
    vector<size_t> m_size;
};

class Solution {
public:
    vector<int> numIslands2(int m, int n, vector<vector<int>>& positions) {

        struct point
        {
            int x;
            int y;

            auto adjacent()
            {
                return array
                {
                    point{x + 1, y},
                    point{x - 1, y},
                    point{x, y + 1},
                    point{x, y - 1}
                };
            }
        };

        if(m == 0 || n == 0) return vector<int>(positions.size(), 0);
        auto grid = vector<vector<int>>(m, vector<int>(n, 0));
        auto uf = disjoint_set{static_cast<size_t>(m * n)};
        auto is_valid_land = [&](point pt)
        {
            return pt.x >= 0 && pt.y >= 0
            && pt.x < m && pt.y < n
            && grid[pt.x][pt.y] == 1;
        };
        auto to_index = [&](point pt)
        {
            return static_cast<size_t>(pt.x * n + pt.y);
        };

        auto cnt = int{};
        auto res = vector<int>{};

        for(const auto& pos : positions)
        {
            auto pt = point{pos[0], pos[1]};
            if(grid[pt.x][pt.y] == 1)
            {
                res.push_back(res.back());
                continue;
            }
            grid[pt.x][pt.y] = 1;
            ++cnt;

            for(auto adj : pt.adjacent())
            {
                if(is_valid_land(adj) && uf.connect(to_index(adj), to_index(pt)))
                {
                    --cnt;
                }
            }

            res.push_back(cnt);
        }

        return res;
    }
};

code

class UnionFind
{
public:
    explicit UnionFind(int num)
            :tree(num)
            ,size(num,1)
    {
        iota(tree.begin(), tree.end(), 0);
    }

    int find(int idx);
    bool connect(int idx1, int idx2);

private:
    vector<int> tree;
    vector<int> size;
};

int UnionFind::find(int idx)
{
    if(tree[idx] != idx)
    {
        tree[idx] = find(tree[idx]);
    }
    return tree[idx];
}

bool UnionFind::connect(int idx1, int idx2)
{
    int rt1 = find(idx1);
    int rt2 = find(idx2);

    if(rt1 == rt2) return false;

    if(size[rt1] < size[rt2])
    {
        tree[rt1] = rt2;
        size[rt2] += size[rt1];
    }
    else
    {
        tree[rt2] = rt1;
        size[rt1] += size[rt2];
    }

    return true;
}

class Solution {

private:
    int count;
    int numRow;
    int numCol;
    UnionFind* set;
    vector<vector<char>>* mat;

    void connect(int x1, int y1, int x2, int y2)
    {
        if(set->connect(x1 * numCol + y1, x2 * numCol + y2) )
            --count;
    }

public:
    vector<int> numIslands2(int m, int n, vector<vector<int>>& positions) {
        // initilize
        count = 0;
        numRow = m;
        numCol = n;
        set = new UnionFind{numRow * numCol};
        mat = new vector<vector<char>>(numRow, vector<char>(numCol, 0));
        vector<int> res{};

        for(auto& pos : positions)
        {
            int x = pos.front();
            int y = pos.back();
            // check if duplicated
            if (1 == (*mat)[x][y])
            {
                res.push_back(count);
                continue;
            }

            (*mat)[x][y] = 1;
            ++count;

            if (x != 0 && 1 == (*mat)[x - 1][y])
            {
                connect(x, y, x-1, y);
            }
            if (y != 0 && 1 == (*mat)[x][y - 1])
            {
                connect(x, y, x, y - 1);
            }
            if (x != m - 1 && 1 == (*mat)[x + 1][y])
            {
                connect(x, y, x + 1, y);
            }
            if (y != n - 1 && 1 == (*mat)[x][y + 1])
            {
                connect(x, y, x, y + 1);
            }

            res.push_back(count);
        }

        delete set;
        delete mat;

        return res;

    }
};