【算法与数据结构】684、685、LeetCode冗余连接I II

文章目录

  • 一、684、冗余连接 I
  • 二、685、冗余连接 II
  • 三、完整代码

所有的LeetCode题解索引，可以看这篇文章——【算法和数据结构】LeetCode题解。

一、684、冗余连接 I

在这里插入图片描述
在这里插入图片描述

  思路分析：题目给出一个无向有环图，要求去掉一个边以后构成一个树（多叉树）。那么我们根据并查集理论，将所有的边加入到并查集中，前面的边先连上，边上的两个节点如果不在同一个集合中，就加入集合。如果两个节点已经出现在同一集合里，说明这两个节点已经连接在一起了，再加入一条后来的边就会构成环。因此去掉后来的这条边即可。

  程序如下：

class Solution {
private:int n = 200005;		// 节点数量 200000vector<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;      // 根不同，则令v的父节点为u}
public: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 join(edges[i][0], edges[i][1]);}return { };}
};

复杂度分析：

  • 时间复杂度： O ( n l o g n ) O(nlogn) O(nlogn)，其中 n n n是图中边的个数，即edges数组的大小。需要遍历图中的 n n n条边，对于每条边，需要对两个节点查找祖先，如果两个节点的祖先不同则需要进行合并，需要进行2次查找和最多1次合并。一共需要进行 2 n 2n 2n次查找和最多 n n n次合并，因此总时间复杂度是 O ( 2 n log ⁡ ⁡ n ) = O ( n log ⁡ n ) O(2n \log ⁡n)=O(n \log n) O(2nlog⁡n)=O(nlogn)。
  • 空间复杂度： O ( n ) O(n) O(n)，主要开销用于father数组。

二、685、冗余连接 II

在这里插入图片描述
在这里插入图片描述

  思路分析：题目说明，图原本是一棵树，只不过在不增加节点的情况下多了一条额外的边，我们需要把多出来的这一条边去除。与684题区别在于本题是有向图，684题是无向图。关于有向图有出度和入度的说法。出度是指节点发出的箭头数量，入度是指指向节点的箭头数量。根节点没有父节点，其他节点有且只有一个父节点，那么多出来的一条边就会改变了节点的入度数量，而出度的数量无法成为判断标准（一个父节点可以由多个子节点，出度数量不唯一）。出现入度为2的节点有以下两种情况：

在这里插入图片描述

  如果加入的这条边形成了有向环，那么入度不会改变：
在这里插入图片描述
  统计节点入度：

int inDegree[N] = {0}; // 记录节点入度
n = edges.size(); // 边的数量
for (int i = 0; i < n; i++) {inDegree[edges[i][1]]++; // 统计入度
}

  前两种入度为2的情况一定是删除入度为2的节点的两条边其中一条。题目还要求返回最后出现在二维数组的答案，也就是说要从后往前遍历，删除以后判断剩下的图是否构成树。如果说两条边都可以构成树，就删除最后一条边。

vector<int> vec; // 记录入度为2的边（如果有的话就两条边）
// 找入度为2的节点所对应的边，注意要倒序，因为优先返回最后出现在二维数组中的答案
for (int i = n - 1; i >= 0; i--) {if (inDegree[edges[i][1]] == 2) {vec.push_back(i);}
}
// 处理图中情况1 和 情况2
// 如果有入度为2的节点，那么一定是两条边里删一个，看删哪个可以构成树
if (vec.size() > 0) {if (isTreeAfterRemoveEdge(edges, vec[0])) {return edges[vec[0]];} else {return edges[vec[1]];}
}

  情况三，明确没有入度为2的情况，一定是有环，我们从后往前遍历，找到删除以后的那个可以构成树的边。那么如何判断一个图是否为树，应该应用到并查集了。因为如果两个点所在的边在添加图之前如果就可以在并查集里找到了相同的根，那么这条边添加上之后 这个图一定不是树了。

// 情况三：在有向图里找到删除的那条边，使其变成树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];}join(edges[i][0], edges[i][1]);}return {};}

  程序如下：

// 685、冗余连接II-并查集
class Solution2 {
private:static const int N = 1005;		// 节点数量 1005int 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]);    // 路径压缩}// 判断 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;      // 根不同，则令v的父节点为u}// 情况三：在有向图里找到删除的那条边，使其变成树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];}join(edges[i][0], edges[i][1]);}return {};}// 删一条边之后判断是不是树bool isTreeAfterRemoveEdge(const vector<vector<int>>& edges, int deleteEdge) {init(); // 初始化并查集for (int i = 0; i < n; i++) {if (i == deleteEdge) continue;if (isSame(edges[i][0], edges[i][1])) { // 构成有向环了，一定不是树return false;}join(edges[i][0], edges[i][1]);}return true;}
public: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的边（如果有的话就两条边）// 找入度为2的节点所对应的边，注意要倒序，因为优先返回最后出现在二维数组中的答案for (int i = n - 1; i >= 0; i--) {if (inDegree[edges[i][1]] == 2) {vec.push_back(i);}}// 情况一和情况二：如果有入度为2的节点，那么一定是两条边里删一个，看删哪个可以构成树if (vec.size() > 0) {if (isTreeAfterRemoveEdge(edges, vec[0])) {return edges[vec[0]];}else {return edges[vec[1]];}}// 情况三：明确没有入度为2的情况，那么一定有有向环，找到构成环的边返回就可以了return getRemoveEdge(edges);}
};

复杂度分析：

  • 时间复杂度： O ( n log ⁡ n ) O(n \log n) O(nlogn)。
  • 空间复杂度： O ( n ) O(n) O(n)。

三、完整代码

# include <iostream>
# include <vector>
using namespace std;// 684、冗余连接I-并查集
class Solution {
private:int n = 200005;		// 节点数量 200000vector<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;      // 根不同，则令v的父节点为u}
public: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 join(edges[i][0], edges[i][1]);}return { };}
};// 685、冗余连接II-并查集
class Solution2 {
private:static const int N = 1005;		// 节点数量 1005int 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]);    // 路径压缩}// 判断 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;      // 根不同，则令v的父节点为u}// 情况三：在有向图里找到删除的那条边，使其变成树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];}join(edges[i][0], edges[i][1]);}return {};}// 删一条边之后判断是不是树bool isTreeAfterRemoveEdge(const vector<vector<int>>& edges, int deleteEdge) {init(); // 初始化并查集for (int i = 0; i < n; i++) {if (i == deleteEdge) continue;if (isSame(edges[i][0], edges[i][1])) { // 构成有向环了，一定不是树return false;}join(edges[i][0], edges[i][1]);}return true;}
public: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的边（如果有的话就两条边）// 找入度为2的节点所对应的边，注意要倒序，因为优先返回最后出现在二维数组中的答案for (int i = n - 1; i >= 0; i--) {if (inDegree[edges[i][1]] == 2) {vec.push_back(i);}}// 情况一和情况二：如果有入度为2的节点，那么一定是两条边里删一个，看删哪个可以构成树if (vec.size() > 0) {if (isTreeAfterRemoveEdge(edges, vec[0])) {return edges[vec[0]];}else {return edges[vec[1]];}}// 情况三：明确没有入度为2的情况，那么一定有有向环，找到构成环的边返回就可以了return getRemoveEdge(edges);}
};int main() {//   // 684、冗余连接I-并查集-测试案例//vector<vector<int>> edges = { {1, 2}, {1, 3}, {2, 3} };//Solution s1;//vector<int> result = s1.findRedundantConnection(edges);// 685、冗余连接II-并查集-测试案例vector<vector<int>> edges = { {1, 2}, {1, 3}, {2, 3} };Solution2 s2;vector<int> result = s2.findRedundantDirectedConnection(edges);for (vector<int>::iterator it = result.begin(); it < result.end(); it++) {cout << *it << ' ';}cout << endl;system("pause");return 0;
}

end

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://xiahunao.cn/news/2804562.html

如若内容造成侵权/违法违规/事实不符，请联系瞎胡闹网进行投诉反馈，一经查实，立即删除！

相关文章

如何在VSCode中带有参数的Debug（name、program、$file、args、pickArgs、指定虚拟环境）

如何在VSCode中带有参数的Debug（name、program、$file、args、pickArgs、指定虚拟环境）

0. 省流 {"version": "0.2.0","configurations": [{"name": "调试train.py文件","type": "debugpy","request": "launch","program": "train.py","cons…
阅读更多...
如何改变.net托管的入口main函数

如何改变.net托管的入口main函数

有小伙伴问: .NET托管入口Main函数可以修改成别的函数&#xff0c;用来作为程序的入口吗&#xff1f; 答案&#xff1a;当然是可以的。这也算是.NET里面非常简单的骚操了。本篇来用最新的.NET8演示下&#xff0c;如何修改Main入口。 1.简单控制台例子&#xff1a; namespace…
阅读更多...
美国硅谷大带宽服务器|大带宽服务器租赁贵吗?

美国硅谷大带宽服务器|大带宽服务器租赁贵吗?

在数字化时代&#xff0c;服务器成为了支撑各种在线业务和应用程序的重要基石。尤其对于那些需要处理大量数据、保证快速响应和稳定连接的企业或个人来说&#xff0c;大带宽服务器成为了不可或缺的选择。而美国硅谷&#xff0c;作为全球科技创新的摇篮&#xff0c;其服务器租赁…
阅读更多...
Open CASCADE学习|绘制砂轮

Open CASCADE学习|绘制砂轮

今天绘制一个砂轮&#xff0c;其轮廓由两条直线段和两段圆弧构成&#xff0c;圆弧分别与直线相切&#xff0c;两条圆弧之间相交而非相切。建模思路是&#xff1a;先给定两条直线段的起始点及长度&#xff0c;画出直线段&#xff0c;然后给定其中一圆弧的半径及圆心角&#xff0…
阅读更多...
python程序设计基础：字符串与正则表达式

python程序设计基础：字符串与正则表达式

第四章&#xff1a;字符串与正则表达式 4.1字符串 最早的字符串编码是美国标准信息交换码ASCII&#xff0c;仅对10个数字、26个大写英文字母、26个小写英文字母及一些其他符号进行了编码。ASCII码采用1个字节来对字符进行编码&#xff0c;最多只能表示256个符号。 随着信息技…
阅读更多...
【新手易错点】golang中byte和rune

【新手易错点】golang中byte和rune

1 总体区别 在Golang中&#xff0c;byte和rune是两种不同类型的数据。简单来说&#xff0c;byte是一个8位的无符号整数类型&#xff0c;而rune则是一个32位的Unicode字符类型。 Byte: 在Golang中&#xff0c;byte类型实际上是uint8的别名&#xff0c;它用来表示8位的无符号整…
阅读更多...
flutter使用getx实现路由跳转，页面没有执行dispose

flutter使用getx实现路由跳转，页面没有执行dispose

我们看一下flutter的StatefulWidget组件的生命周期&#xff1a; createState&#xff1a; 当一个StatefulWidget插入到渲染树结构、或者从渲染树结构移除时&#xff0c;都会调用StatefulWidget.createState方法&#xff0c;从而达到更新UI的效果&#xff1b; initState&#…
阅读更多...
【刷题记录】链表的回文结构

【刷题记录】链表的回文结构

本系列博客为个人刷题思路分享&#xff0c;有需要借鉴即可。 1.题目链接&#xff1a; LINK 2.详解思路&#xff1a; 思路&#xff1a;思路&#xff1a;先找到中间节点&#xff0c;然后逆置后半部分链表&#xff0c;一个指针指向链表的头节点&#xff0c;再一个指针指向逆置的头…
阅读更多...
怎么在wifi中实现手机和电脑文件互传

怎么在wifi中实现手机和电脑文件互传

有时我们想手机电脑文件互传&#xff0c;数据线却不在身边&#xff0c;这时我们可以用MiXplorer来实现wifi中手机和电脑互相访问文件。 MiXplorer是一款来自著名安卓开发者论坛XDA的作品&#xff0c;免费且功能强大&#xff0c;被很多人誉为是“全能文件管理器”。 1.在手机上…
阅读更多...
Golin 弱口令/漏洞/扫描/等保/基线核查的快速安全检查小工具

Golin 弱口令/漏洞/扫描/等保/基线核查的快速安全检查小工具

下载地址&#xff1a; 链接&#xff1a;https://pan.quark.cn/s/db6afba6de1f 主要功能 主机存活探测、漏洞扫描、子域名扫描、端口扫描、各类服务数据库爆破、poc扫描、xss扫描、webtitle探测、web指纹识别、web敏感信息泄露、web目录浏览、web文件下载、等保安全风险问题风险…
阅读更多...
进程线程通信-day6

进程线程通信-day6

1、将信号和消息队列的课堂代码敲一遍 //发送端 #include<myhead.h>//定义一个消息结构类型 struct msgbuf {long mtype;char mtext[1024]; }; //定义一个宏&#xff0c;表示消息正文大小 #define MSGSIZE sizeof(struct msgbuf)-sizeof(long)int main(int argc, const…
阅读更多...
CSS实现半边边框（只有边框的部分可见）

CSS实现半边边框（只有边框的部分可见）

CSS实现半边边框&#xff08;只有边框的部分可见&#xff09; <div class"part box"><h1>内容</h1><!-- 绘出下面两个对角边框--><div class"part-footer"></div> </div>主要代码 .box {width: 100px;height:…
阅读更多...
cmake 项目。qt5升级 qt6 报错 error: “Qt requires a C++17 compiler 已解决

cmake 项目。qt5升级 qt6 报错 error: “Qt requires a C++17 compiler 已解决

日常项目开发中。需要对qt5升级到qt6 做cmake兼容配置&#xff0c;在编译中发现&#xff0c;有c 编译环境 报错 2>C:\Qt\6.5.3\msvc2019_64\include\QtCore/qcompilerdetection.h(1226,1): fatal error C1189: #error: "Qt requires a C17 compiler, and a suitable …
阅读更多...
ChatGPT的增长已经进入了瓶颈期

ChatGPT的增长已经进入了瓶颈期

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…
阅读更多...
Vue3自定义组件v-model双向绑定

Vue3自定义组件v-model双向绑定

无能吐槽一下&#xff0c;虽然用了很多遍v-model&#xff0c;但是还是不得要领&#xff0c;每次看官网都感觉说的不是很清晰&#xff0c;在写的时候还是要查看文档&#xff0c;可能就是不理解原理&#xff0c;这次特意好好写一篇文章&#xff0c;让自己好好理解一下。 自定义一…
阅读更多...
React18源码: React调度中的3种优先级类型和Lane的位运算

React18源码: React调度中的3种优先级类型和Lane的位运算

优先级类型 React内部对于优先级的管理&#xff0c;贯穿运作流程的4个阶段&#xff08;从输入到输出&#xff09;&#xff0c;根据其功能的不同&#xff0c;可以分为3种类型&#xff1a; 1 &#xff09;fiber优先级(LanePriority) 位于 react-reconciler包&#xff0c;也就是L…
阅读更多...
HarmonyOS Stage模型 应用配置文件讲解

HarmonyOS Stage模型 应用配置文件讲解

好&#xff0c;上文 HarmonyOS Stage模型基本概念讲解 中&#xff0c;我们简单讲解了HarmonyOS 中 Stage模型的基本概念 那么 我们继续学习Stage模型的相关知识 上文之后 我们肯定对它的概念和基本结构 有了一个了解 那么 我们就来看一下 基于Stage模型 它里面一些基本的配置文…
阅读更多...
FPGA领域顶级学术会议

FPGA领域顶级学术会议

FPGA领域顶级学术会议主要有FPGA，FCCM，FPL和FPT。 1 FPGA 会议全名是: ACM/SIGDA International Symposium on Field-Programmable Gate Arrays 网站是:https://dl.acm.org/conference/fpga FPGA常年在美国举办，每年2月，偏FPGA基础研究； 该会议的论文免费下载。这个比…
阅读更多...
Java项目：26 基于SpringBoot+thymeleaf实现的蓝天幼儿园管理系统

Java项目：26 基于SpringBoot+thymeleaf实现的蓝天幼儿园管理系统

作者主页&#xff1a;舒克日记 简介&#xff1a;Java领域优质创作者、Java项目、学习资料、技术互助 文中获取源码 项目介绍 基于SpringBootthymeleaf实现的蓝天幼儿园管理系统是为幼儿园提供的一套管理平台&#xff0c;可以提高幼儿园信息管理的准确性&#xff0c;系统将信息…
阅读更多...
数据结构D4作业

数据结构D4作业

1.实现单向循环链表的功能 loop.c #include "loop.h" loop_p create_loop() { loop_p H(loop_p)malloc(sizeof(loop)); if(HNULL) { printf("创建失败\n"); return NULL; } H->len0; H->nextH; ret…
阅读更多...
最新文章

Copyright @ 2022~2023