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

2024-02-24 06:44
文章标签 leetcode 算法 连接 数据结构 ii 冗余 685 684

本文主要是介绍【算法与数据结构】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

这篇关于【算法与数据结构】684、685、LeetCode冗余连接I II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/741271。

相关文章

哈希leetcode-1

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素（O(1)） 当我们要频繁的查找某个元素，第一哈希表O(1)，第二，二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储，只要开26个c
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
W外链微信推广短连接怎么做？

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

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

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
秋招最新大模型算法面试，熬夜都要肝完它

秋招最新大模型算法面试，熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候，不知道面试完会不会复盘、总结，做笔记的习惯，这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助，都附有完整答案，熬夜也要看完，祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN，还有完整版的大模型 AI 学习资料，朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2