并查集|1971. 寻找图中是否存在路径、684.冗余连接、685.冗余连接II

2024-03-25 05:36

本文主要是介绍并查集|1971. 寻找图中是否存在路径、684.冗余连接、685.冗余连接II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

并查集基础

1971. 寻找图中是否存在路径

684.冗余连接

685.冗余连接II


并查集基础

并查集主要有三个功能。

  1. 寻找根节点,函数:find(int u),也就是判断这个节点的祖先节点是哪个
  2. 将两个节点接入到同一个集合,函数:join(int u, int v),将两个节点连在同一个根节点上
  3. 判断两个节点是否在同一个集合,函数:isSame(int u, int v),就是判断两个节点是不是同一个根节点

并查集模板如下:

int n = 1005; // n根据题目中节点数量而定,一般比节点数量大一点就好
vector<int> father = vector<int> (n, 0); // C++里的一种数组结构// 并查集初始化
void init() {for (int i = 0; i < n; ++i) {father[i] = i;}
}
// 并查集里寻根的过程
int find(int u) {return u == father[u] ? u : father[u] = find(father[u]); // 路径压缩
}// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {u = find(u);v = find(v);return u == v;
}// 将v->u 这条边加入并查集
void join(int u, int v) {u = find(u); // 寻找u的根v = find(v); // 寻找v的根if (u == v) return ; // 如果发现根相同,则说明在一个集合,不用两个节点相连直接返回father[v] = u;
}

 

1971. 寻找图中是否存在路径

题目链接

有一个具有 n个顶点的 双向 图,其中每个顶点标记从 0 到 n - 1(包含 0 和 n - 1)。图中的边用一个二维整数数组 edges 表示,其中 edges[i] = [ui, vi] 表示顶点 ui 和顶点 vi 之间的双向边。 每个顶点对由 最多一条 边连接,并且没有顶点存在与自身相连的边。

请你确定是否存在从顶点 start 开始,到顶点 end 结束的 有效路径 。

给你数组 edges 和整数 n、start和end,如果从 start 到 end 存在 有效路径 ,则返回 true,否则返回 false 。

思路:本题是并查集基础题目。并查集可以解决什么问题呢?

主要就是集合问题,两个节点在不在一个集合,也可以将两个节点添加到一个集合中。

所以这里遍历图,分别将各个连接元素加入并查集里,最后判断给定元素是否联通

class Solution {
public:int n=200005;vector<int>father=vector<int>(n,0);void init(){//并查集初始化for(int i=0;i<n;++i) father[i]=i;}//并查集寻根int find(int u){return u==father[u] ? u:father[u]=find(father[u]);}//判断u,v是否同根bool isSame(int u, int v){u=find(u);v=find(v);return u==v;}//将v->u这条边加入并查集void joint(int u, int v){u=find(u);v=find(v);//找到V,U的根if(u==v)return;//如果同根,说明在同一个并查集里,不用相连了father[v]=u;}bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {init();for(int i=0;i<edges.size();i++){//依次将各边加入并查集joint(edges[i][0], edges[i][1]);}return isSame(source,destination);//判断是否在并查集里}
};

684.冗余连接

力扣题目链接

树可以看成是一个连通且 无环 的 无向 图。

给定往一棵 n 个节点 (节点值 1~n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间,且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ,edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。

请找出一条可以删去的边,删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案,则返回数组 edges 中最后出现的边。

 思路:

题目说是无向图,返回一条可以删去的边,使得结果图是一个有着N个节点的树(即:只有一个根节点)。

如果有多个答案,则返回二维数组中最后出现的边。

那么我们就可以从前向后遍历每一条边(因为优先让前面的边连上),边的两个节点如果不在同一个集合,就加入集合(即:同一个根节点)。

如图所示:

节点A 和节点 B 不在同一个集合,那么就可以将两个 节点连在一起。

(如果题目中说:如果有多个答案,则返回二维数组中最前出现的边。 那我们就要 从后向前遍历每一条边了)

如果边的两个节点已经出现在同一个集合里,说明着边的两个节点已经连在一起了,再加入这条边一定就出现环了。

如图所示:

已经判断 节点A 和 节点B 在在同一个集合(同一个根),如果将 节点A 和 节点B 连在一起就一定会出现环。

class Solution {
public:int n=1005;vector<int>father=vector<int>(n,0);void init(){for(int i=0;i<n;++i){father[i]=i;}}int find(int u){return u==father[u]? u:father[u]=find(father[u]);}int isSame(int u, int v){u=find(u);v=find(v);return u==v;}void joint(int u, int v){u=find(u);v=find(v);if(u==v)return;father[v]=u;}vector<int> findRedundantConnection(vector<vector<int>>& edges) {init();for(int i=0;i<edges.size();i++){if(isSame(edges[i][0], edges[i][1]))return edges[i];else joint(edges[i][0], edges[i][1]);}return {};}
};

 

685.冗余连接II

力扣题目链接

在本问题中,有根树指满足以下条件的 有向 图。该树只有一个根节点,所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点,而根节点没有父节点。

输入一个有向图,该图由一个有着 n 个节点(节点值不重复,从 1 到 n)的树及一条附加的有向边构成。附加的边包含在 1 到 n 中的两个不同顶点间,这条附加的边不属于树中已存在的边。

结果图是一个以边组成的二维数组 edges 。 每个元素是一对 [ui, vi],用以表示 有向 图中连接顶点 ui 和顶点 vi 的边,其中 ui 是 vi 的一个父节点。

返回一条能删除的边,使得剩下的图是有 n 个节点的有根树。若有多个答案,返回最后出现在给定二维数组的答案。

 

思路:

该图由一个有着N个节点 (节点值不重复1, 2, ..., N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间,这条附加的边不属于树中已存在的边。

这说明题目中的图原本是是一棵树,只不过在不增加节点的情况下多加了一条边!

还有**若有多个答案,返回最后出现在给定二维数组的答案。**这说明在两条边都可以删除的情况下,要删顺序靠后的!

那么有如下三种情况,前两种情况是出现入度为2的点,如图:

且只有一个节点入度为2,为什么不看出度呢,出度没有意义,一棵树中随便一个父节点就有多个出度。

第三种情况是没有入度为2的点,那么图中一定出现了有向环(注意这里强调是有向环!

如图:

首先先计算节点的入度,edges[i][1] 表示的节点都是 箭头指向的节点,即这个几点有一个入度! (如果想统计出度,那么就是 edges[i][0])。

前两种入度为2的情况,一定是删除指向入度为2的节点的两条边其中的一条,如果删了一条,判断这个图是一个树,那么这条边就是答案,同时注意要从后向前遍历,因为如果两条边删哪一条都可以成为树,就删最后那一条。

在来看情况三,明确没有入度为2的情况,那么一定有向环,找到构成环的边就是要删除的边。可以定义一个函数,代码如下:

// 在有向图里找到删除的那条边,使其变成树,返回值就是要删除的边
vector<int> getRemoveEdge(const vector<vector<int>>& edges)

大家应该知道了,我们要实现两个最为关键的函数:

  • isTreeAfterRemoveEdge() 判断删一个边之后是不是树了
  • getRemoveEdge 确定图中一定有了有向环,那么要找到需要删除的那条边

此时应该是用到并查集了,并查集为什么可以判断 一个图是不是树呢?

因为如果两个点所在的边在添加图之前如果就可以在并查集里找到了相同的根,那么这条边添加上之后 这个图一定不是树了

class Solution {
public:static const int N=1005;//并查集大小int father[N];int n;//边数量void init(){for(int i=0;i<=n;i++){father[i]=i;}}int find(int u){return u==father[u]?u:father[u]=find(father[u]);}void joint(int u, int v){u=find(u);v=find(v);if(u==v)return;father[v]=u;}bool isSame(int u, int v){u=find(u);v=find(v);return u==v;}//在有向图里查找要删除的边,使其变成树vector<int> getRemoveEdge(const vector<vector<int>>& edges){init();//初始化并查集for(int i=0;i<n;i++){if(isSame(edges[i][0], edges[i][1]))return edges[i];joint(edges[i][0], edges[i][1]);}return {};}//删除一条边后判断是否为树bool isTree(const vector<vector<int>>& edges, int deletedEdege){init();for(int i=0; i<n;i++){if(i==deletedEdege)continue;if(isSame(edges[i][0], edges[i][1])){return false;//构成环了}joint(edges[i][0], edges[i][1]);}return true;}vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {int indegree[N]={0};//记录节点入度;n=edges.size();//边数量for(int i=0;i<n;i++){indegree[edges[i][1]]++;}vector<int>vec;//记录入度为2的节点,如果有的话就两条边for(int i=n-1;i>=0;i--){if(indegree[edges[i][1]]==2)vec.push_back(i);}//处理无环的两种情况,看删除哪条边可以构成树if(vec.size()>0){if(isTree(edges, vec[0]))return edges[vec[0]];else return edges[vec[1]];}//处理情况3,有环时return getRemoveEdge(edges);}
};

参考:代码随想录 

这篇关于并查集|1971. 寻找图中是否存在路径、684.冗余连接、685.冗余连接II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/843980

相关文章

MySQL中的表连接原理分析

《MySQL中的表连接原理分析》:本文主要介绍MySQL中的表连接原理分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、背景2、环境3、表连接原理【1】驱动表和被驱动表【2】内连接【3】外连接【4编程】嵌套循环连接【5】join buffer4、总结1、背景

SpringBoot连接Redis集群教程

《SpringBoot连接Redis集群教程》:本文主要介绍SpringBoot连接Redis集群教程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 依赖2. 修改配置文件3. 创建RedisClusterConfig4. 测试总结1. 依赖 <de

SpringBoot项目配置logback-spring.xml屏蔽特定路径的日志

《SpringBoot项目配置logback-spring.xml屏蔽特定路径的日志》在SpringBoot项目中,使用logback-spring.xml配置屏蔽特定路径的日志有两种常用方式,文中的... 目录方案一:基础配置(直接关闭目标路径日志)方案二:结合 Spring Profile 按环境屏蔽关

python判断文件是否存在常用的几种方式

《python判断文件是否存在常用的几种方式》在Python中我们在读写文件之前,首先要做的事情就是判断文件是否存在,否则很容易发生错误的情况,:本文主要介绍python判断文件是否存在常用的几种... 目录1. 使用 os.path.exists()2. 使用 os.path.isfile()3. 使用

java连接opcua的常见问题及解决方法

《java连接opcua的常见问题及解决方法》本文将使用EclipseMilo作为示例库,演示如何在Java中使用匿名、用户名密码以及证书加密三种方式连接到OPCUA服务器,若需要使用其他SDK,原理... 目录一、前言二、准备工作三、匿名方式连接3.1 匿名方式简介3.2 示例代码四、用户名密码方式连接4

VSCode设置python SDK路径的实现步骤

《VSCode设置pythonSDK路径的实现步骤》本文主要介绍了VSCode设置pythonSDK路径的实现步骤,包括命令面板切换、settings.json配置、环境变量及虚拟环境处理,具有一定... 目录一、通过命令面板快速切换(推荐方法)二、通过 settings.json 配置(项目级/全局)三、

MySQL 表的内外连接案例详解

《MySQL表的内外连接案例详解》本文给大家介绍MySQL表的内外连接,结合实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录表的内外连接(重点)内连接外连接表的内外连接(重点)内连接内连接实际上就是利用where子句对两种表形成的笛卡儿积进行筛选,我

使用Python和Matplotlib实现可视化字体轮廓(从路径数据到矢量图形)

《使用Python和Matplotlib实现可视化字体轮廓(从路径数据到矢量图形)》字体设计和矢量图形处理是编程中一个有趣且实用的领域,通过Python的matplotlib库,我们可以轻松将字体轮廓... 目录背景知识字体轮廓的表示实现步骤1. 安装依赖库2. 准备数据3. 解析路径指令4. 绘制图形关键

Apache 高级配置实战之从连接保持到日志分析的完整指南

《Apache高级配置实战之从连接保持到日志分析的完整指南》本文带你从连接保持优化开始,一路走到访问控制和日志管理,最后用AWStats来分析网站数据,对Apache配置日志分析相关知识感兴趣的朋友... 目录Apache 高级配置实战:从连接保持到日志分析的完整指南前言 一、Apache 连接保持 - 性

电脑蓝牙连不上怎么办? 5 招教你轻松修复Mac蓝牙连接问题的技巧

《电脑蓝牙连不上怎么办?5招教你轻松修复Mac蓝牙连接问题的技巧》蓝牙连接问题是一些Mac用户经常遇到的常见问题之一,在本文章中,我们将提供一些有用的提示和技巧,帮助您解决可能出现的蓝牙连接问... 蓝牙作为一种流行的无线技术,已经成为我们连接各种设备的重要工具。在 MAC 上,你可以根据自己的需求,轻松地