【数据结构与算法】并查集

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6

😀大家好我是白晨一个不是很能熬夜😫但是也想日更的人✈。如果喜欢这篇文章点个赞👍关注一下👀白晨吧你的支持就是我最大的动力💪💪💪

在这里插入图片描述

文章目录

前言

大家好我是白晨这次为大家带来的数据结构是并查集这是一种能够快速合并两个集合以及快速查询两个元素是否在一个集合中时间复杂度在大量查询的情况下可以达到O(1)的数据结构由于实现思路简单代码短性质好经常会在算法题中用到。同时并查集也在与图相关的算法中出现过很多次例如最小生成树Kruskal算法就使用了并查集。

img

并查集

🚗定义及实例

并查集 英文Disjoint-set data structure直译为不交集数据结构是一种数据结构 用于处理一些不交集 Disjoint sets一系列没有重复元素的集合的合并及查询问题。并查集支持如下操作

  • 查询查询某个元素属于哪个集合通常是返回集合内的一个"代表元素"。这个操作是为了判断两个元素是否在同一个集合之中。

  • 合并将两个集合合并为一个。

举个例子有小明、小亮、小虎、小李、小王、小孙六个学生已知小明和小孙是同学小王和小明是同学小亮和小李是同学小虎和小孙是同学。

  • 问小虎和小王是什么关系小李和小王是什么关系

image-20230130203524181

按照常识我们可以把互为同学的学生划入同一个集合如果两个同学的名字在同一个集合中出现那么这两个人互为同学。反之两个人不是同学。

image-20230130203119960

观察上图小虎和小王是同学关系小李和小王不是同学关系。

上面就是并查集的简单应用并查集能够快速合并两个集合以及快速查询两个元素是否在一个集合中时间复杂度在大量查询的情况下可以达到O(1)。

🚓实现

并查集要实现的操作就两种——合并和查询只要抓住并查集的核心思路并查集的实现是非常简单的白晨给出两种实现方式作为参考一种是工程向的实现方式另一种是算法竞赛向的实现方式两种实现方式的思想是不变的重点是体会并查集的思想。

🥚工程向实现

  • 存储结构数组
  • 初始化数组元素全部初始化为-1。
  • 存储数据根节点为负数其绝对值为集合中元素的个数孩子结点中存放父节点的下标。
class UnionFindSet
{
public:
	// 默认全部都无父节点为-1
	UnionFindSet(size_t sz)
		:_ufs(sz, -1)
	{}
private:
	vector<int> _ufs; // 根节点为负数其绝对值为集合中元素的个数孩子结点中存放父节点的序号
};
  • 查询

并查集最核心的操作就是查询元素集合的根如果两个元素集合的根相同说明两个元素在同一个集合中。子节点存放的是父节点的下标只需要向上查找就能找到根。

image-20230130210320997

具体实现

// 核心代码查找一个子集的根
int FindRoot(int x)
{
	int root = x;
	// 查找到结点权值为负的根
	while (_ufs[root] >= 0)
	{
		root = _ufs[root];
	}
	return root;
}

但是如果树的层数太高我们就无法保证O(1)的时间复杂度所以我们做一优化每查询一次将查询的节点到根的所有结点直接连接到根结点上。

// 核心代码查找一个子集的根
int FindRoot(int x)
{
	int root = x;
	// 查找到结点权值为负的根
	while (_ufs[root] >= 0)
	{
		root = _ufs[root];
	}

	// 优化将被查找结点及路径上直接连接到根
	int cur = x;
	while (_ufs[cur] >= 0)
	{
		int parent = _ufs[cur];
		_ufs[cur] = root;
		cur = parent;
	}
	return root;
}

重复迭代的代码太长我们也可以使用递归实现两行代码完成查找+路径优化

// 根结点查找 + 路径优化
int FindRoot(int x)
{
	if (_ufs[x] >= 0) _ufs[x] = FindRoot(_ufs[x]);
	return _ufs[x];
}
  • 合并

查找两个要合并元素的根节点根节点相同则不用合并如果两个根节点不同则将随便将其中一个集合的根节点连接到另一个集合根节点下。代码中的优化可要可不要对于效率影响不大。

具体实现

// 合并两个集合
bool Union(int x, int y)
{
	int xroot = FindRoot(x);
	int yroot = FindRoot(y);
	// xy为同一个集合的话合并失败
	if (xroot == yroot)
		return false;

	// 优化数据量小的结点并入数据量大的结点可要可不要
	// if (abs(_ufs[xroot]) < abs(_ufs[yroot]))
		// swap(xroot, yroot);
    
	_ufs[xroot] += _ufs[yroot];
	_ufs[yroot] = xroot;
	return true;
}
  • 工程向实现参考代码
#include <iostream>
#include <string>
#include <vector>

using namespace std;

class UnionFindSet
{
public:
	// 默认全部都无父节点为-1
	UnionFindSet(size_t sz)
		:_ufs(sz, -1)
	{}
	
	// 合并两个集合
	bool Union(int x, int y)
	{
		int xroot = FindRoot(x);
		int yroot = FindRoot(y);
		// xy为同一个集合的话合并失败
		if (xroot == yroot)
			return false;

		// 优化数据量小的结点并入数据量大的结点
		if (abs(_ufs[xroot]) < abs(_ufs[yroot]))
			swap(xroot, yroot);
		// 默认并入xroot要保证xroot的数据量大
		_ufs[xroot] += _ufs[yroot];
		_ufs[yroot] = xroot;
		return true;
	}

	// 核心代码查找一个子集的根
	int FindRoot(int x)
	{
		int root = x;
		// 查找到结点权值为负的根
		while (_ufs[root] >= 0)
		{
			root = _ufs[root];
		}

		// 优化将被查找结点及以上的结点直接连接到根
		int cur = x;
		while (_ufs[cur] >= 0)
		{
			int parent = _ufs[cur];
			_ufs[cur] = root;
			cur = parent;
		}
		return root;
	}

	// 获取有多少个集合
	int SetCount()
	{
		int cnt = 0;
		for (int e : _ufs)
		{
			if (e < 0)
				cnt++;
		}
		return cnt;
	}

	// 查询两个元素是否在同一个集合中
	bool IsInSet(int x, int y)
	{
		return FindRoot(x) == FindRoot(y);
	}
private:
	vector<int> _ufs; // 根节点为负数其绝对值为集合中元素的个数孩子结点中存放父节点的序号
};

🍳算法向实现

  • 存储结构数组
  • 初始化数组元素全部初始化为-1。
  • 存储数据根节点为负数其绝对值为集合中元素的个数孩子结点中存放父节点的下标。

实现思路与工程向实现基本相同只是算法向实现直接开好一个大数组作为并查集。

#include <iostream>

using namespace std;

const int N = 100010;

int p[N]; // 并查集

// 根结点查找 + 路径优化
int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void merge(int x, int y)
{
    p[find(x)] = find(y);
}

🚕相关例题

题目练习中的代码使用算法向的实现下面的例题都是并查集相关的应用希望大家可以将其掌握。

🎉合并集合

image-20221231191847308

🍬原题链接合并集合

🪅算法思想

并查集基本实现 + 应用。

🪆代码实现

  • 并查集的元素初始化为自身下标方便理解。
// 模板并查集
#include <iostream>

using namespace std;

const int N = 100010;

int p[N];

// 根结点查找 + 路径优化
int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void merge(int x, int y)
{
    p[find(x)] = find(y);
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) p[i] = i;

    while (m--)
    {
        char op[2];
        int x, y;
        scanf("%s%d%d", op, &x, &y);

        if (op[0] == 'M') merge(x, y);
        else
        {
            if (find(x) == find(y)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}
  • 并查集的元素初始化为-1可以保存一个集合中的元素个数。
// 初始化为-1版本可以保存集合个数
#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

const int N = 100010;

int p[N];

// 两种find函数的实现递归 和 迭代任取其一即可
// 根结点查找 + 路径优化
int find(int x)
{
    if (p[x] >= 0) p[x] = find(p[x]);
    else return x;
}

// 根结点查找 + 路径优化
int find(int x)
{
    int cur = x;
    vector<int> v;
    // 循环结束时cur为根结点坐标
    while (p[cur] >= 0)
    {
        v.push_back(cur);
        cur = p[cur];
    }
    // 将路径上的结点全部直接连接到cur节点上
    for (auto e : v) p[e] = cur;
    return cur;
}

void merge(int x, int y)
{
    if (find(x) != find(y))
    {
        p[find(y)] += p[find(x)];
        p[find(x)] = find(y);
    }
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    memset(p, -1, 4 * N);

    while (m--)
    {
        char op[2];
        int x, y;
        scanf("%s%d%d", op, &x, &y);

        if (op[0] == 'M') merge(x, y);
        else
        {
            if (find(x) == find(y)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

🧨连通块中点的数量

image-20221231220311875

🍬原题链接连通块中点的数量

🪅算法思想

基本的并查集应用下面给出两种实现方式

  • 并查集的元素初始化为-1此时根节点的绝对值就为此集合的元素个数。
  • 并查集的元素初始化为自身下标额外维护一个数组存储集合中元素个数。

🪆代码实现

  • 并查集的元素初始化为-1可以保存一个集合中的元素个数。
// 初始化为-1版本
#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010;

int p[N];

// 根结点查找 + 路径优化
int find(int x)
{
    if (p[x] >= 0) p[x] = find(p[x]);
    else return x;
}

void merge(int x, int y)
{
    if (find(x) != find(y))
    {
        p[find(y)] += p[find(x)];
        p[find(x)] = find(y);
    }
}

int size(int x)
{
    return abs(p[find(x)]);
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    memset(p, -1, 4 * N);

    while (m--)
    {
        char op[3];
        int x, y;
        scanf("%s", op);

        if (op[0] == 'C')
        {
            scanf("%d%d", &x, &y);
            merge(x, y);
        }
        else if (op[1] == '1')
        {
            scanf("%d%d", &x, &y);
            if (find(x) == find(y)) puts("Yes");
            else puts("No");
        }
        else
        {
            scanf("%d", &x);
            printf("%d\n", size(x));
        }
    }
    return 0;
}
  • 并查集的元素初始化为自身下标维护一个存储结点个数的数组。
#include <iostream>

using namespace std;

const int N = 100010;

int p[N], s[N]; // p为父节点数组s为集合大小数组

// 根结点查找 + 路径优化
int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void merge(int x, int y)
{
    // 合并时要先判断是否是同一个集合的
    if (find(x) != find(y))
    {
        // 头节点的数量才有效
        s[find(y)] += s[find(x)];
        p[find(x)] = find(y);
    }
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) p[i] = i, s[i] = 1;

    while (m--)
    {
        char op[3];
        int x, y;
        scanf("%s", op);

        if (op[0] == 'C')
        {
            scanf("%d%d", &x, &y);
            merge(x, y);
        }
        else if (op[1] == '1')
        {
            scanf("%d%d", &x, &y);
            if (find(x) == find(y)) puts("Yes");
            else puts("No");
        }
        else
        {
            scanf("%d", &x);
            printf("%d\n", s[find(x)]);
        }
    }
    return 0;
}

✨食物链

image-20221231220829442

🍬原题链接食物链

🪅算法思想

并查集的元素初始化为自身下标额外维护一个距离根节点路径长度的数组。规定

  • x 和 y 为同类x到根节点的距离 和 y到根节点的距离同余3x到根节点的距离和y到根节点的距离模3都为0。
  • x 吃 y x到根节点的距离mod3 - y到根节点的距离mod 3 = 1。

🪆代码实现

#include <iostream>

using namespace std;

const int N = 50010;

int p[N], d[N]; // p为堆d为每个结点到根节点的距离d可以为负

int find(int x)
{
    if (p[x] != x)
    {
        int root = find(p[x]); // 先找到根节点并且将从根节点到父节点的距离全部更新
        d[x] += d[p[x]];// 现在到根的距离 等于 自己原本到父节点的距离 + 父节点到根的距离已在上面递归中更新
        p[x] = root;
    }
    return p[x];
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) p[i] = i;
    int ans = 0;

    while (m--)
    {
        int op, x, y;
        scanf("%d%d%d", &op, &x, &y);

        if (x > n || y > n) ans++;
        else
        {
            int rx = find(x), ry = find(y);
            if (op == 1)
            {
                // 当是同一个集合 并且 不是一个种类时
                if (rx == ry && (d[x] - d[y]) % 3 != 0) ans++;
                else if (rx != ry) // 不是一个集合将其合并
                {
                    d[rx] = d[y] - d[x]; // rx并入ry后(d[rx] + d[x] - d[y]) % 3 = 0取特殊解d[rx] + d[x] - d[y] = 0
                    p[rx] = ry;
                }
                // 还有一种情况就是同一个集合同一个种类这个情况不用管所以就不讨论了
            }
            else
            {
                // x 吃 y则 (d[x] - d[y] - 1) % 3 = 0
                if (rx == ry && (d[x] - d[y] - 1) % 3 != 0) ans++;
                else if (rx != ry) // 不是一个集合建立关系
                {
                    d[rx] = d[y] - d[x] + 1; // rx并入ry后(d[rx] + d[x] - d[y] - 1) % 3 = 0取特殊解d[rx] + d[x] - d[y] - 1 = 0
                    p[rx] = ry;
                }
            }
        }
    }

    printf("%d\n", ans);
    return 0;
}

后记

未来在图相关的算法中我们还会使用使用并查集希望大家可以尽快掌握一起加油吧

如果解析有不对之处还请指正我会尽快修改多谢大家的包容。

如果大家喜欢这个系列还请大家多多支持啦😋

如果这篇文章有帮到你还请给我一个大拇指 👍和小星星 ⭐️支持一下白晨吧喜欢白晨【算法】或【数据结构】系列的话不如关注👀白晨以便看到最新更新哟

我是不太能熬夜的白晨我们下篇文章见。

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6
返回列表

上一篇：【正点原子FPGA连载】第二十六章gpio子系统简介 摘自【正点原子】DFZU2EG

下一篇：带你手撕排序算法

“【数据结构与算法】并查集” 的相关文章

人大金仓数据库分区表1年前 (2023-02-02)
如何在快速迭代开发中写清楚需求，提高与软件工程师的沟通效率1年前 (2023-02-02)
高并发环境下构建缓存服务，你需要注意这6点1年前 (2023-02-02)
Cocos Creator 打包原生 Android 包该如何选择 NDK 版本？1年前 (2023-02-02)
《数据结构》八大排序（详细图文分析讲解）1年前 (2023-02-02)
数据库课程设计—超市零售信息管理系统（Python实现）_超市管理系统数据库设计1年前 (2023-02-02)
【微服务-架构选型】记录2022年微服务技术架构选型1年前 (2023-02-02)
【Linux】文件系统1年前 (2023-02-02)
谷粒学院——Day11【首页数据显示和添加Redis缓存】1年前 (2023-02-02)
基于百度智能云的OCR接口进行图文识别1年前 (2023-02-02)

阿里云国际版