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

在这里插入图片描述

文章目录

前言

大家好，我是白晨，这次为大家带来的数据结构是并查集，这是一种能够快速合并两个集合以及快速查询两个元素是否在一个集合中，时间复杂度在大量查询的情况下可以达到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);
	// x，y为同一个集合的话合并失败
	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);
		// x，y为同一个集合的话合并失败
		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到根节点的距离同余3（x到根节点的距离和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;
}

后记

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

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

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

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

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

# 数据结构 # 算法 # c++ # c语言 # leetcode
Logo
2048 AI社区

有“AI”的1024 = 2048，欢迎大家加入2048 AI社区

更多推荐

cover

智能体效率优化最新综述：从Token狂飙到成本可控的进化之路

avatar 2048 AI社区
cover

告别加班熬夜：打工人必备的 paperzz AI PPT 神器

avatar 2048 AI社区
cover

效率革命来袭：paperzz AI PPT 一键重塑职场演示新体验

avatar 2048 AI社区