并查集：简单认识与模拟

海棠未眠

发布于 2025-10-22 15:37:47

8200

代码可运行

运行总次数：0

代码可运行

一、什么是并查集

并查集（Disjoint-Set Union，DNF）是一种用于高效处理 不相交集合 合并与查询的数据结构。

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

譬如，加里敦大学的25招生计算机班中共招有20名学生，分别来自全国各地。其中成都3人，绵阳2人，新乡2人，郑州5人，西安5人，南阳3人。起初，这20个学生属于不同的高中，所以每个个体都是一个独立的集合。随后在信息统计中，我们会把些学生按照城市划分，再然后，把这些城市又按照省份划分到四川，陕西，河南三个省份的集合。

又譬如，某公司今年校招全国总共招生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担任队长，负责大家的出行。

一趟火车之旅后，每个小分队成员就互相熟悉，称为了一个朋友圈。但是小分队与小分队之间却是不相识的。

上面0,1,2之间目前是没有任何关系线连接起来。编号6,7,8同学属于0号小分队，该小分队中有4人(包含队长0)；编号为4和9的同学属于1号小分队，该小分队有3人(包含队长1)，编号为3和5的同学属于2号小分队，该小分队有3个人(包含队长2)。

根据上面图形，以及各个编号之间关系我们可以得出结论：

1. 数组的下标对应集合中元素的编号

2. 数组中如果为负数，负号代表根，数字代表该集合中元素个数

3. 数组中如果为非负数，代表该元素双亲在数组中的下标

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

现在0集合有7个人，2集合有3个人，总共两个朋友圈。

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

1. 查找元素属于哪个集合

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

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

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

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

将两个集合中的元素合并

将一个集合名称改成另一个集合的名称

4. 集合的个数

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

二、并查集的实现

#include<iostream>
#include<vector>

class UnionFindSet
{
public:
	UnionFindSet(size_t size)
		:
		_ufs(size, -1)//我们默认初始化数组时都初始化为-1，表示他们一开始都是以个体为单位的集合
	{}
private:
	std::vector<int> _ufs;//最底层其实是个数组来实现的
};

通过上面的图例可以看出，并查集的底层逻辑其实是通过数组来实现的，我们默认数组的每个元素初始化为-1，把他们都当做以个体为单位的集合。并查集所主要使用的方法有两种：查找根以及合并两个集合。

查找根节点：我们上面说过，-号代表这个元素是他所在集合的根，元素的绝对值大小是他所在集合的元素个数。所以查找就需要判断元素的数值：

#include<iostream>
#include<vector>

class UnionFindSet
{
public:
	UnionFindSet(size_t size)
		:
		_ufs(size, -1)
	{}
    size_t Find_root(size_t pos)
    {
    	while (_ufs[pos] >= 0)//不断循环查找直至找到元素为负数的位置，这个就是所在集合的根
	    {
		    pos = _ufs[pos];
	    }
	    return pos;
    }
private:
	std::vector<int> _ufs;/
};

当我们找到根之后，就可以轻松进行两个集合的合并操作：

#include<iostream>
#include<vector>

class UnionFindSet
{
public:
	UnionFindSet(size_t size)
		:
		_ufs(size, -1)
	{}

	size_t Find_root(size_t pos)
	{
		while (_ufs[pos] >= 0)
		{
			pos = _ufs[pos];
		}
		return pos;
	}

	bool Union(size_t x, size_t y)//将x与y所在集合合并
	{
		size_t root1 = Find_root(x);
		size_t root2 = Find_root(y);
		
		if (root1 != root2)
		{
			_ufs[root1] += _ufs[root2];
			_ufs[root2] = root1;
			return true;
		}
		else
		{
			return false;
		}
	}
private:
	std::vector<int> _ufs;
};

最后，我们可以写一个count函数来返回这个并查集内不同集合的个数，原理也十分简单，我们都知道根的值都是负数，那么数组有多少个负数，就有多少个根，从而得到是集合的个数。

class UnionFindSet
{
public:
	UnionFindSet(size_t size)
		:
		_ufs(size, -1)//我们默认初始化数组时都初始化为-1，表示他们一开始都是以个体为单位的集合
	{}

	size_t Find_root(size_t pos)
	{
		while (_ufs[pos] >= 0)//不断循环查找直至找到元素为负数的位置，这个就是所在集合的根
		{
			pos = _ufs[pos];
		}
		return pos;
	}

	bool Union(size_t x, size_t y)//将x与y所在集合合并
	{
		size_t root1 = Find_root(x);
		size_t root2 = Find_root(y);
		
		if (root1 != root2)
		{
			_ufs[root1] += _ufs[root2];
			_ufs[root2] = root1;
			return true;
		}
		else
		{
			return false;
		}
	}
	size_t count()//负数值的个数就代表有多少棵树
	{
		size_t ret = 0;
		for (auto& it : _ufs)
		{
			if (it < 0)
			{
				ret++;
			}
		}
		return ret;
	}
private:
	std::vector<int> _ufs;//最底层其实是个数组来实现的
};

一个简单的并查集就实现成功啦！

三、并查集的补充知识

1. 路径压缩优化

原始的Find_root可能导致树过高，通过路径压缩可将查找路径上的节点直接指向根节点：

size_t Find_root(size_t pos) 
{
    if (_ufs[pos] >= 0) 
    {
        _ufs[pos] = Find_root(_ufs[pos]); // 递归压缩路径
    }
    return _ufs[pos] < 0 ? pos : _ufs[pos];
}

效果：将树压平，后续查询时间复杂度接近O(1)。

2. 按秩合并优化

在合并时避免树的不平衡增长，额外维护一个_rank数组记录树高：

bool Union(size_t x, size_t y) 
{
    size_t root1 = Find_root(x), root2 = Find_root(y);
    if (root1 == root2) 
        return false;
    
    if (_rank[root1] < _rank[root2]) 
    {
        std::swap(root1, root2);
    }
    _ufs[root1] += _ufs[root2];
    _ufs[root2] = root1;
    if (_rank[root1] == _rank[root2]) 
    {
        _rank[root1]++;
    }
    return true;
}

优势：保证树高不超过O(log n)。