当前位置：首页 > article >正文

【高阶数据结构】并查集

article 2024/11/24 5:14:33

> 作者：დ旧言~
> 座右铭：松树千年终是朽，槿花一日自为荣。

> 目标：了解什么是并查集，并能简单的模拟实现。

> 毒鸡汤：有些事情，总是不明白，所以我不会坚持。早安!

> 专栏选自：数据结构

> 望小伙伴们点赞👍收藏✨加关注哟💕💕

一、并查集的原理

概念：

在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个单元素集合, 然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一个元素归属于那个集合的运算。适合于描述这类问题的抽象数据类型称为并查集(union-find set)。

举个栗子：

某旅游团内有游客10人，其中西安4人，成都3人，武汉3人，10个人来自不同的地方，起先互不相识，每个游客都是一个独立的小团体，现给这些游客进行编号：{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; 给以下数组用来存储该小集体，数组中的数字代表：该小集团中具有成员的个数（负数的意义下文讲解）

旅行结束后，游客们要乘车回家，每个地方的游客自发组织成小分队一起上路，于是：西安游客小分队s1={0,6,7,8}，成都游客小分队s2={1,4,9}，武汉游客小分队s3={2,3,5}就相互认识了，10个人形成了三个小团体。假设右三个群主0,1,2担任队长，负责大家的出行。

一趟火车之旅后，每个小分队成员就互相熟悉，称为了一个朋友圈。

总结：

数组的下标对应集合中元素的编号。
数组中如果为负数，负号代表根，数字代表该集合中元素个数。
数组中如果为非负数，代表该元素双亲在数组中的下标。

在公司工作一段时间后，西安小分队中8号同学与成都小分队1号同学奇迹般的走到了一起，两个
小圈子的学生相互介绍，最后成为了一个小圈子：

通过以上例子可知，并查集一般可以解决一下问题：

查找元素属于哪个集合

沿着数组表示树形关系以上一直找到根(即：树中中元素为负数的位置)。

查看两个元素是否属于同一个集合

沿着数组表示的树形关系往上一直找到树的根，如果根相同表明在同一个集合，否则不在。

将两个集合归并成一个集合

将两个集合中的元素合并。
将一个集合名称改成另一个集合的名称。

集合的个数

遍历数组，数组中元素为负数的个数即为集合的个数。

二、并查集的实现

并查集功能说明：

查找元素属于哪个集合。
查看两个元素是否属于同一个集合。
将两个集合归并成一个集合。
集合的个数。

代码实现：

#include <iostream>
#include <vector>
 
class UnionFind {
private:
    std::vector<int> parent;
    std::vector<int> rank;
 
public:
    UnionFind(int n) : parent(n), rank(n) {
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
            rank[i] = 1;
        }
    }
 
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }
 
    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) return;
 
        if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else {
            parent[rootY] = rootX;
            rank[rootX] += 1;
        }
    }
 
    bool connected(int x, int y) {
        return find(x) == find(y);
    }
};
 
int main() {
    int n, m;
    std::cin >> n >> m;
    UnionFind uf(n);
    for (int i = 0; i < m; ++i) {
        int a, b;
        std::cin >> a >> b;
        uf.unite(a - 1, b - 1); // 转换为0-based索引
    }
    for (int i = 0; i < m; ++i) {
        int a, b;
        std::cin >> a >> b;
        std::cout << (uf.connected(a - 1, b - 1) ? "YES" : "NO") << std::endl;
    }
    return 0;
}

三、并查集的应用

省份数量

class Solution {
public:
    size_t FindRoot(int x)
    {
        while(ufs[x] >= 0)
        {
            x = ufs[x];
        }
        return x;
    }
    int findCircleNum(vector<vector<int>>& isConnected) {
        ufs.resize(isConnected.size(), -1);
        for(int i = 0; i < isConnected.size(); i++)
        {
            for(int j = 0; j < isConnected[i].size(); j++)
            {
                if(isConnected[i][j] == 1)
                {
                    int root1 = FindRoot(i);
                    int root2 = FindRoot(j);
                    if(root1 != root2)
                    {
                        if(abs(ufs[root1]) < abs(ufs[root2]))
                            swap(root1, root2);
                        ufs[root1] += ufs[root2];
                        ufs[root2] = root1;
                    }
                }
            }
        }
        int cnt = 0;
        for(auto& e : ufs)
            if(e < 0) cnt++;
        return cnt;            
    }
private:
    vector<int> ufs;
};

等式方程的可满足性

class Solution {
public:
    int Find(int x)
    {
        while(ufs[x] >= 0)
            x = ufs[x];
        return x;
    }
    bool equationsPossible(vector<string>& equations) {
        ufs.resize(26, -1);
        for(auto& str : equations)
        {
            if(str[1] == '=')
            {
                int root1 = Find(str[0]-'a');
                int root2 = Find(str[3]-'a');
                if(root1 != root2)
                {
                    if(abs(ufs[root1]) < abs(ufs[root2]))
                        swap(root1, root2);
                    ufs[root1] += ufs[root2];
                    ufs[root2] = root1;
                }
            }
        }
        for(auto& str : equations)
        {
            if(str[1] == '!')
            {
                int root1 = Find(str[0]-'a');
                int root2 = Find(str[3]-'a');
                if(root1 == root2)
                    return false;
            }
        }
        return true;
    }
private:
    vector<int> ufs;
};