并查集实现及其应用

article/2025/8/26 16:53:19

先看看度娘给出的定义吧:

并查集,在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中。其特点是看似并不复杂,但数据量极大,若用正常的数据结构来描述的话,往往在空间上过大,计算机无法承受;即使在空间上勉强通过,运行的时间复杂度也极高,根本就不可能在比赛规定的运行时间(1~3秒)内计算出试题需要的结果,只能用并查集来描述。

总结一下:

如果我们有大量的元素集合,我们需要频繁的调用以下两个操作:

  • 将两个元素区间合并
  • 判断两个元素是否在一个集合

如果我们没有并查集,那在面对大量数据下,执行这两个操作的时间复杂度将会很高

而如果我们使用并查集这个结构,虽然单次操作的时间复杂度可能为O(n),但如果我们频繁地调用这两个函数,平均下来的时间复杂度可达到O(1)

这个结论我们不证明,(毕竟大佬都证明了20多年才证出来,我咋可能在这么短的时间证出来(小声))

咳咳,总言而之,大家把上面的结论记住就行了

并查集这种结构可以很好的解决一些需要统计集合个数的题目

目录

  • 并查集的实现
  • 并查集应用
    • 力扣547,省份数量
    • 力扣200,岛屿数量

并查集的实现

先给出一个定义:

指针指向自己的结点,我们把它叫做这个集合的代表结点,它是作为标识集合的最顶点(父结点)存在的

假如我们有一个整数数组,我们需要实现成并查集

在这里插入图片描述

我们在初始化的时候,我们先把每个元素都看做一个单独的集合

也就是出一个指针,指向自己

在这里插入图片描述

这样就完成了我们的初始化,也就是每个元素的代表结点都是它本身

所以,我们判断元素是否来自同一个集合就很简单了,直接判断它们的代表结点是否相同即可

合并的操作如下:

现在这种情况,假如我们要合并1,2这两个元素所在的集合,我们可以把其中某个元素集合的父节点挂在另外一个父结点就行了

我们不妨把2挂在1上面

在这里插入图片描述

这样我们就完成了一次元素合并

假如我们这次要把2和3合并在一起,怎么做?

同样的,把其中一个集合的父节点挂在另外一个元素的父节点就行了

但这种情况,需要注意,为了加快效率,我们通常把小集合的父节点挂在大集合的父节点上

就像这样

在这里插入图片描述
但这个过程中,我们还需要一些操作

比如怎么找到某个元素所在集合的代表节点?怎么实现快速查找代表结点?在下面的代码实现中详细介绍

我们需要以下结构来实现:

一个记录元素关键结点下标位置的数组,一个记录当前元素所在集合的大小,还需要记录当前集合的个数

vector<int>parent;//记录此位置的关键结点,比如:parent[i]=a,代表i下标的元素在a处
vector<int>size;//记录关键结点所在集合的大小,只对关键结点有效,非关键结点设为0
vector<int>help;//辅助数组,后面做介绍
int sets;//记录当前并查集集合个数

初始化时,我们需要知道并查集初始有多少个元素,根据初始每个元素一个集合这个设定,可以快速写出以下初始化代码:

int n = nums.size();//我们的数组中有多少个元素,初始就开多少集合
parent.resize(n);
size.resize(n);
help.resize(n);
sets = n;for (int i = 0; i < n; i++)
{parent[i] = i;//关键结点为自己size[i] = 1;//集合大小为1
}

因为上面的操作中,需要频繁的查找关键结点的位置,所以还需要实现一个查找关键结点位置的函数

原理很简单:

如果某个元素的parent[i]记录的下标不是元素本身的下标,就代表此结点不是代表结点,我们就通过parent数组记录的位置找到那个下标,不断迭代,直到找到关键结点为止

//这个函数最后返回当前下标中元素的代表结点下标int findfather(int i){while (i != parent[i]){i = parent[i];}return i;}

但在某种极端情况下,这样频繁的调用的话,每次调用的时间复杂度都为O(n)

比如:元素都在一条链上,组成了一个类似链表的结构,我们从最下面的元素查找

在这里插入图片描述
如果我们不做任何优化的话,时间复杂度平均下来还是O(n)

我们可以做压缩路径的优化

具体实现如下:

我们每次遍历时,把元素存在help数组中,就像下面

在这里插入图片描述
然后进行路径压缩,我们把依次弹出help中的每个元素,然后把每个元素的代表结点都设为当前返回值

在这里插入图片描述
这样每个元素就全部指向唯一的代表结点了

总结:

前面提到的help数组在这里当做栈来使用

虽然单次查找的时间复杂度可能是O(n),但经过了我们的路径压缩后,以后如果重复查找这个集合中的元素的话,时间复杂度就为O(1)

因为我们的前提是大量重复操作,所以平均下面,时间复杂度还是O(1)

完整的查找代表结点代码:

	int findfather(int i){int hi = 0;while (i != parent[i]){help[hi++] = i;i = parent[i];}for (hi--; hi >= 0; hi--)//记住先--{parent[help[hi]] = i;//路径压缩操作help[hi] = 0;}return i;}

接下来我们来实现文章开头提到的两个方法

注意:我们使用这两个方法时,参数传原数组中的下标

查找是否为相同元素就很简单了,直接判断相等即可

	bool isSameFather(int i, int j){return findfather(i) == findfather(j);}

合并时的操作如下

先分别找出元素所在集合的代表结点

int A = findfather(i);
int B = findfather(j);

这时判断一下,如果A=B,代表两个元素来自同一集合,就不需要进行合并操作,直接函数退出即可

因为我们是将小集合挂在大集合上,所以我们需要判断一下A,B中哪个是大集合

int big = size[A] >= size[B] ? A : B;
int small = big == A ? B : A;

然后执行合并操作:改变代表结点位置,改变size值,改变集合个数等

parent[small] = big;
size[big] += size[small];
size[small] = 0;
sets--;//合并一个就代表并查集中集合少了一个

大多数情况下,我们可能还需要返回并查集中元素的个数

	int getSets(){return sets;}

完整代码如下

class Union2
{
public:Union2(vector<int>& nums){int n = nums.size();parent.resize(n);size.resize(n);help.resize(n);sets = n;for (int i = 0; i < n; i++){parent[i] = i;size[i] = 1;}}bool isSameFather(int i, int j){return findfather(i) == findfather(j);}int getSets(){return sets;}void together(int i, int j)//传的是下标{int A = findfather(i);int B = findfather(j);if (A != B){int big = size[A] >= size[B] ? A : B;int small = big == A ? B : A;parent[small] = big;size[big] += size[small];size[small] = 0;sets--;}}
private:vector<int>parent;//记录此位置的关键结点vector<int>size;//记录关键结点的位置vector<int>help;//做栈int sets;//记录集合个数int findfather(int i){int hi = 0;while (i != parent[i]){help[hi++] = i;i = parent[i];}for (hi--; hi >= 0; hi--)//记住先--{parent[help[hi]] = i;help[hi] = 0;}return i;}
};

另外再补充一下哈希表的实现,把哈希把当做指针结点来进行保存即可,其它无异

class Node
{
public:Node(int x):val(x){}private:int val;
};class Union
{private:unordered_map<int, Node*>node;//值和值对应的结点unordered_map<Node*, Node*>parent;//结点和其代表结点unordered_map<Node*, int>size;//代表结点和对应其集合大小Node* findfather(Node* n){stack<Node*>path;Node* cur = n;while (parent[cur] != cur){cur = parent[cur];path.push(cur);}if (!path.empty()){Node* now = path.top();parent[now] = cur;path.pop();}return cur;}public:Union(vector<int>& nums){for (auto i:nums){Node* n = new Node(i);node[i] = n;parent[n] = n;size[n] = 1;}}bool isSameUnion(int a, int b){return findfather(node[a]) == findfather(node[b]);}int setsize(){return size.size();}void together(int a, int b){Node* A = findfather(node[a]);Node* B = findfather(node[b]);if (A != B){Node* big = size[A] >= size[B] ? A : B;Node* small = A == big ? B : A;parent[small] = big;size[big] += size[small];size.erase(small);}}
};

并查集应用

力扣547,省份数量

原题链接

题目描述:

有 n 个城市,其中一些彼此相连,另一些没有相连。如果城市 a 与城市 b 直接相连,且城市 b 与城市 c 直接相连,那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市,组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ,其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连,而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。

例如:输入:isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出:2(因为1,2城市有联系,那么1,2其中一个就不是首都)

思路求解:

这道题是一个典型的并查集返回集合个数的问题

如果有0,1,2这三个城市,设0,1,2分别代表数组中的横纵坐标,如果它们之间有道路,则把它们在数组中的交点设为1,反之为0

我们可以得出数组的以下性质:对角线上元素恒为1,因为自己跟自己肯定有联系

此数组一定是一个对称矩阵,如果(1,2)之间有联系,那么(2,1)也必然有联系

所以我们在遍历时,只需要遍历数组对角线上面的元素即可

因为初始有行数个城市,所以我们初始化并查集时,只需传进行数大小即可,初始每个城市都是首都,也就是每个结点都是代表结点

如果遍历到有联系,合并这两个城市即可

代码如下:

class Union//并查集集合
{
public:Union(int n)//有多少城市就传入多少,初始假设每个城市都是首都{parent.resize(n);size.resize(n);help.resize(n);set=n;for(int i=0;i<n;i++){parent[i]=i;//初始的父亲结点指向自己size[i]=1;//每个集合仅有一个元素}}bool isSameFather(int i,int j)//观察是否属于同一个元素{return findFather(i)==findFather(j);}void together(int i,int j)//将两个元素的集合合并{int A=findFather(i);int B=findFather(j);//先找到它们的代表结点if(A!=B)//不等才操作{//为了提高效率,将小集合挂在大集合下面int big=A>=B?A:B;int small=big==A?B:A;parent[small]=big;//将代表结点改变即可size[big]+=size[small];size[small]=0;set--;}}int getSet(){return set;}private:vector<int>parent;//表示某个下标位置的父亲在哪里vector<int>size;//表示代表结点的集合个数vector<int>help;//在压缩路径时当做栈使用int set;//记录集合个数int findFather(int i)//传入下标,把代表结点的下标返回{int hi=0;while(parent[i]!=i)//判断当然元素的父亲是不是自己,是就停止,不是就迭代{help[hi++]=i;i=parent[i];}//进行路径压缩for(hi--;hi>=0;hi--){parent[help[hi]]=i;help[hi]=0;}return i;}
};class Solution {
public:int findCircleNum(vector<vector<int>>& isConnected) {int n=isConnected.size();Union u(n);for(int i=0;i<n;i++){for(int j=i+1;j<n;j++)//只需要遍历右上角的元素{if(isConnected[i][j]==1){u.together(i,j);}}}return u.getSet();}
};

力扣200,岛屿数量

原题链接

给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。
岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外,你可以假设该网格的四条边均被水包围。

例如:

输入:grid = [
[“1”,“1”,“0”,“0”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“1”,“0”,“0”],
[“0”,“0”,“0”,“1”,“1”]
]
输出:3

思路求解

这题其实有一个递归感染法,不过不是本章重点,所以我只贴出代码,不详细讲解

class Solution {
public:void infect(vector<vector<char>>& grid,int r,int c){//感染的时候为了防止死递归,将数字都改为2if(r<0||c<0||r>=grid.size()||c>=grid[0].size()||grid[r][c]!='1'){return;}grid[r][c]='2';infect(grid,r-1,c);infect(grid,r+1,c);infect(grid,r,c-1);infect(grid,r,c+1);}int numIslands(vector<vector<char>>& grid) {//递归感染法int ans=0;int r=grid.size();int c=grid[0].size();for(int i=0;i<r;i++){for(int j=0;j<c;j++){if(grid[i][j]=='1'){ans++;infect(grid,i,j);}}}return ans;}
};

我们重点讲解这题的并查集实现方法

首先,设地图有row行,有col列,那么我们在初始化时可以开一个row*col的数组

我们可以把二维坐标转化为一维数组,转化公式如下:

int index(int i,int j)
{return i*col+j;
}

初始时,我们先遍历整个地图,只要有岛,就将其对应坐标初始化,初始时每个1都看做一个独立的岛

为了防止漏数,所以在我们遍历的时候,观察当然位置的左上位置是否有岛,有就合并

int index(vector<vector<char>>& grid,int i,int j)
{return i*grid[0].size()+j;
}class Union2
{
public:Union2(vector<vector<char>>& grid){//特别注意这题并查集的构造//把并查集转成一维数组,在二维数组下标对应位置存储元素,其它不做处理,遍历在每个1时才对并查集对应位置做处理int n=grid.size()*grid[0].size();parent.resize(n);size.resize(n);help.resize(n);sets=0;for(int i=0;i<grid.size();i++){for(int j=0;j<grid[0].size();j++){if(grid[i][j]=='1'){int k=index(grid,i,j);parent[k]=k;size[k]++;sets++;//集合数动态增加}}}}bool isSameFather(int i, int j){return findfather(i) == findfather(j);}int getSets(){return sets;}void together(int i, int j)//传的是下标{int A = findfather(i);int B = findfather(j);if (A != B){int big = size[A] >= size[B] ? A : B;int small = big == A ? B : A;parent[small] = big;size[big] += size[small];size[small] = 0;sets--;}}
private:vector<int>parent;//记录此位置的关键结点vector<int>size;//记录关键结点的位置vector<int>help;//做栈int sets;//记录集合个数int findfather(int i){int hi = 0;while (i != parent[i]){help[hi++] = i;i = parent[i];}for (hi--; hi >= 0; hi--)//记住先--{parent[help[hi]] = i;help[hi] = 0;}return i;}
};class Solution {
public:int numIslands(vector<vector<char>>& grid) {Union2 u(grid);for(int j=1;j<grid[0].size();j++){if(grid[0][j-1]=='1'&&grid[0][j]=='1'){u.together(index(grid,0,j-1),index(grid,0,j));}}for(int i=1;i<grid.size();i++){if(grid[i-1][0]=='1'&&grid[i][0]=='1'){u.together(index(grid,i-1,0),index(grid,i,0));}}
//前面两个for循环是对边界的处理for(int i=1;i<grid.size();i++){for(int j=1;j<grid[0].size();j++){if(grid[i][j]=='1'){if(grid[i-1][j]=='1'){u.together(index(grid,i-1,j),index(grid,i,j));}if(grid[i][j-1]=='1'){u.together(index(grid,i,j),index(grid,i,j-1));}}}}return u.getSets();}
};

http://chatgpt.dhexx.cn/article/kFVvf6fp.shtml

相关文章

超级简单并查集详解

一、概述 并查集&#xff0c;在一些有N个元素的集合应用问题中&#xff0c;我们通常是在开始时让每个元素构成一个单元素的集合&#xff0c;然后按一定顺序将属于同一组的元素所在的集合合并&#xff0c;其间要反复查找一个元素在哪个集合中。 其实说白了大部分还是用于寻找两…

并查集(java)

介绍 &#xff1a; 并查集属于数据结构的一种 是高等数据结构最基础的一部分&#xff0c;主要分为普通并查集 种类并查集以及带权并查集。它是一种用于管理元素所属集合的数据结构&#xff0c;这里的集合我们可以理解为一颗数 每个元素都是树上的有一个分叉&#xff0c;顺着分叉…

C++并查集

文章目录 并查集的原理并查集的实现代码并查集的典型应用 并查集的原理 在一些应用问题中&#xff0c;需要将n个不同的元素划分成一些不相交的集合。开始时&#xff0c;每个元素自成一个单元素集合&#xff0c;然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用…

c++并查集(详细总结)

老话重谈&#xff0c;先看定义 并查集是一种树型的数据结构&#xff0c;用于处理一些不相交集合&#xff08;disjoint sets&#xff09;的合并及查询问题。常常在使用中以森林来表示。 首先得明白一些概念&#xff1a; 什么是树&#xff0c;什么是森林&#xff08;由树组成的叫…

Java——并查集

概念 当我们将多个元素分配到不同的集合中&#xff0c;这些集合有的是相关的&#xff0c;有的是不相关的。并查集就是用来查找两个元素是否在同一个集合中的 其主要实现方式是&#xff1a;将所有的元素以下标的形式存储在数组中。例如一共有十个人&#xff0c;那么就将这些人…

并查集Python版

以下来自于leetcode 使用数据结构&#xff1a;并查集 思路&#xff1a;由于相等关系具有传递性&#xff0c;所有相等的变量属于同一个集合&#xff1b;只关心连通性&#xff0c;不关心距离&#xff0c;因此很容易想到并查集。&#xff08;很容易嘛&#xff0c;反正我想不到&am…

并查集详解

文章目录 并查集一、简介1.定义2. 并查集的实现与优化 二、练习1.合并集合2.连通块中点的数量3. 食物链 三、总结 并查集 一、简介 1.定义 并查集是一种树型的数据结构&#xff0c;用于处理一些不相交集合的合并及查询问题&#xff08;即所谓的并、查&#xff09;。比如说&am…

带权并查集

带权并查集需要先理解一般的并查集&#xff0c;不明白的可自行先搜索有关内容 一般的并查集主要记录节点之间的链接关系&#xff0c;而没有其他的具体的信息&#xff0c;仅仅代表某个节点与其父节点之间存在联系&#xff0c;它多用来判断图的连通性&#xff0c;如下图所示&…

并查集,不就一并和一查?

什么是并查集 并查集这种数据结构&#xff0c;可能出现的频率不是那么高&#xff0c;但是还会经常性的见到&#xff0c;其理解学习起来非常容易&#xff0c;通过本文&#xff0c;一定能够轻轻松松搞定并查集&#xff01; 对于一种数据结构&#xff0c;肯定是有自己的应用场景和…

数据结构——并查集

并查集是一种数据结构&#xff0c;是树的一种应用&#xff0c;用于处理一些不交集&#xff08;一系列没有重复元素的集合&#xff09;的合并以及查询问题。并查集支持如下操作&#xff1a; 查询&#xff1a;查询某个元素属于哪个集合&#xff0c;通常是返回集合内的一个“代表…

并查集详解(C/C++)

并查集算法详解&#xff08;C&#xff09; 并查集基础并查集是什么&#xff1f;并查集的作用是什么&#xff1f;并查集的结构合并查询 代码实现优化1&#xff1a;避免退化&#xff08;按秩合并&#xff09;代码优化 优化2&#xff1a;路径压缩代码优化 最终代码实现复杂度分析经…

并查集及其应用

并查集的基本操作: 1.合并两个集合 2.查询两个元素的祖宗节点 扩展: 1.记录每个集合的大小 将集合大小绑定到代表元素节点上 就是并查集的思想 (不是每个元素都是正确的 但是代表元素是正确的) 2.记录每个点到根节点的距离 绑定到每个元素身上 因为每个元素到根节点的距离…

并查集(Union-Find) (图文详解)

文章目录 并查集基础知识定义C实现优化 精选算法题(Java实现)实现并查集交换字符串中的元素最长连续序列 - 字节面试常考连通网络的操作次数最大岛屿数量 (三种解法)省份数量冗余连接冗余连接Ⅱ情侣牵手(困难)移除最多的同行或同列石头等式方程的可满足性 结语 并查集基础知识 …

什么是 “并查集” ?

导语&#xff1a;并查集是一种精巧的算法&#xff0c;本身并不难理解&#xff0c;却很常用&#xff0c;在许多场景下都能找到并查集的身影。 本文作者封承成&#xff0c;年仅12岁&#xff0c;非常感谢他的投稿。 并查集是什么 并查集&#xff0c;是一种判断“远房亲戚”的算法。…

并查集(Disjoint Set)

目录 ❤️什么是并查集&#xff1f; &#x1f3b6;实现方法1 &#x1f414;实现方法2 &#x1f383;题目1 ❤️什么是并查集&#xff1f; 并查集是一种数据结构&#xff0c;用于处理一些不交集&#xff08;Disjoint sets&#xff0c;一系列没有重复元素的集合&#xff09;的…

并查集

参考 https://www.cnblogs.com/asdfknjhu/p/12515480.html https://www.bilibili.com/video/BV13t411v7Fs?p3 https://leetcode-cn.com/problems/number-of-provinces/solution/python-duo-tu-xiang-jie-bing-cha-ji-by-m-vjdr/ 一、基本概念 并查集是一种数据结构 并查集这…

并查集(详细解释+完整C语言代码)

目录 1概论 2.树的表现形式 3.代码实现 3.1创立集合 3.2合并 3.3查询 3.4路径压缩 第一个方法&#xff1a;查找时优化 第二个方法&#xff1a;合并时优化&#xff08;加权标记法&#xff09; 4.完整代码 4.1优化前 4.2优化后 1概论 并查集是一种十分精巧且实用的树形…

时间序列预测的一般步骤

一、ARIMA模型概述 ​​ ARMA模型就是AR和MA的简单结合&#xff0c;同时包含了历史数值项和错误项。由于AR和MA模型都对时间序列有平稳性要求&#xff0c;ARMA模型也存在这个限制&#xff0c;因此我们将其拓展到ARIMA模型&#xff0c;其可以解决非平稳性问题。引入的差分概念是…

时间序列预测算法总结

时间序列算法 time series data mining 主要包括decompose&#xff08;分析数据的各个成分&#xff0c;例如趋势&#xff0c;周期性&#xff09;&#xff0c;prediction&#xff08;预测未来的值&#xff09;&#xff0c;classification&#xff08;对有序数据序列的feature提…

基于深度学习的时间序列预测

# 技术黑板报 # 第十一期 推荐阅读时长&#xff1a;15min 前言 时间序列建模历来是学术和工业界的关键领域&#xff0c;比如用于气候建模、生物科学和医学等主题应用&#xff0c;零售业的商业决策和金融等。虽然传统的统计方法侧重于从领域专业知识层面提供参数模型&#xff0…