并查集|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

相关文章

W外链微信推广短连接怎么做?

制作微信推广链接的难点分析 一、内容创作难度 制作微信推广链接时,首先需要创作有吸引力的内容。这不仅要求内容本身有趣、有价值,还要能够激起人们的分享欲望。对于许多企业和个人来说,尤其是那些缺乏创意和写作能力的人来说,这是制作微信推广链接的一大难点。 二、精准定位难度 微信用户群体庞大,不同用户的需求和兴趣各异。因此,制作推广链接时需要精准定位目标受众,以便更有效地吸引他们点击并分享链接

hdu2544(单源最短路径)

模板题: //题意:求1到n的最短路径,模板题#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#i

poj 1734 (floyd求最小环并打印路径)

题意: 求图中的一个最小环,并打印路径。 解析: ans 保存最小环长度。 一直wa,最后终于找到原因,inf开太大爆掉了。。。 虽然0x3f3f3f3f用memset好用,但是还是有局限性。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#incl

poj 1182 并查集 食物链类

题意: 有n只动物,分别编号1....n。所有动物都属于A,B,C中的一种,已知A吃B,B吃C,C吃A。 按顺序给出下面两种共K条信息: 1. x 和 y 属于同一类。 2. x 吃 y 。 然而这些信息可能会出错,有可能有的信息和之前给出的信息矛盾,也有的信息可能给出的 x 和 y 不在n的范围内。 求k条信息中有多少条是不正确的。 解析: 对于每只动物,创建3个元素 i

Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

题目点击打开链接 凸多边形A, 多边形B, 判断B是否严格在A内。  注意AB有重点 。  将A,B上的点合在一起求凸包,如果凸包上的点是B的某个点,则B肯定不在A内。 或者说B上的某点在凸包的边上则也说明B不严格在A里面。 这个处理有个巧妙的方法,只需在求凸包的时候, <=  改成< 也就是说凸包一条边上的所有点都重复点都记录在凸包里面了。 另外不能去重点。 int

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close

Java 连接Sql sever 2008

Java 连接Sql sever 2008 /Sql sever 2008 R2 import java.sql.Connection; import java.sql.DriverManager; import java.sql.ResultSet; import java.sql.Statement; public class TestJDBC

寻找身高相近的小朋友

题目描述: 小明今年升学到小学一年级,来到新班级后发现其他小朋友们身高参差不齐,然后就想基于各小朋友和自己的身高差对他们进行排序,请帮他实现排序。 输入描述: 第一行为正整数H和N,0<H<200,为小明的身高,0<N<50,为新班级其他小朋友个数。第二行为N个正整数H1-HN,分别是其他小朋友的身高,取值范围0<Hi<200(1<=i<=N),且N个正整数各不相同。 输出描述: 输出

实例:如何统计当前主机的连接状态和连接数

统计当前主机的连接状态和连接数 在 Linux 中,可使用 ss 命令来查看主机的网络连接状态。以下是统计当前主机连接状态和连接主机数量的具体操作。 1. 统计当前主机的连接状态 使用 ss 命令结合 grep、cut、sort 和 uniq 命令来统计当前主机的 TCP 连接状态。 ss -nta | grep -v '^State' | cut -d " " -f 1 | sort |

从0到1,AI我来了- (7)AI应用-ComfyUI-II(进阶)

上篇comfyUI 入门 ,了解了TA是个啥,这篇,我们通过ComfyUI 及其相关Lora 模型,生成一些更惊艳的图片。这篇主要了解这些内容:         1、哪里获取模型?         2、实践如何画一个美女?         3、附录:               1)相关SD(稳定扩散模型的组成部分)               2)模型放置目录(重要)