【图轮】【 最小生成树】【 并集查找】1489. 找到最小生成树里的关键边和伪关键边

2024-04-01 00:20
文章标签 查找 最小 生成 关键 找到 并集 1489 树里 图轮

本文主要是介绍【图轮】【 最小生成树】【 并集查找】1489. 找到最小生成树里的关键边和伪关键边，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本文涉及知识点

图轮 最小生成树 并集查找 关键边

1489. 找到最小生成树里的关键边和伪关键边

给你一个 n 个点的带权无向连通图，节点编号为 0 到 n-1 ，同时还有一个数组 edges ，其中 edges[i] = [fromi, toi, weighti] 表示在 fromi 和 toi 节点之间有一条带权无向边。最小生成树 (MST) 是给定图中边的一个子集，它连接了所有节点且没有环，而且这些边的权值和最小。
请你找到给定图中最小生成树的所有关键边和伪关键边。如果从图中删去某条边，会导致最小生成树的权值和增加，那么我们就说它是一条关键边。伪关键边则是可能会出现在某些最小生成树中但不会出现在所有最小生成树中的边。
请注意，你可以分别以任意顺序返回关键边的下标和伪关键边的下标。
示例 1：
在这里插入图片描述

输入：n = 5, edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]
输出：[[0,1],[2,3,4,5]]
解释：上图描述了给定图。
下图是所有的最小生成树。
在这里插入图片描述

注意到第 0 条边和第 1 条边出现在了所有最小生成树中，所以它们是关键边，我们将这两个下标作为输出的第一个列表。
边 2，3，4 和 5 是所有 MST 的剩余边，所以它们是伪关键边。我们将它们作为输出的第二个列表。
示例 2 ：

在这里插入图片描述

输入：n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]
输出：[[],[0,1,2,3]]
解释：可以观察到 4 条边都有相同的权值，任选它们中的 3 条可以形成一棵 MST 。所以 4 条边都是伪关键边。

提示：
2 <= n <= 100
1 <= edges.length <= min(200, n * (n - 1) / 2)
edges[i].length == 3
0 <= fromi < toi < n
1 <= weighti <= 1000
所有 (fromi, toi) 数对都是互不相同的。

最小生成树

n是点数，e是边数。

按边加

按边的权重由低到高排序。依次处理各边 n 1 ↔ n 2 n1 \leftrightarrow n2 n1↔n2
{ 忽略 n 1 , n 2 已经连接 ( 1 ) 加到生成树中 n 1 , n 2 未连接 ( 2 ) \begin{cases} 忽略 && n1,n2已经连接 && (1) \\ 加到生成树中 &&n1,n2未连接 && (2)\\ \end{cases} {忽略加到生成树中​​n1,n2已经连接n1,n2未连接​​(1)(2)​
情况(1): n1 ↔ \leftrightarrow ↔n2 说明 n1到n2存在环 ,删除环上任意边都不影响连通性，而 n 1 ↔ n 2 n1 \leftrightarrow n2 n1↔n2最长，故删除它。
情况(2) 令n1当前所在的连通区域为r1，则r1中的点有且只有一个点会和r1外的点连接(待证一）。令其为n3和n4。 n 3 ↔ n 4 换成 n 1 ↔ n 2 n3 \leftrightarrow n4 换成n1 \leftrightarrow n2 n3↔n4换成n1↔n2 更短。
待证一：如果没有边，则n1无法与n2连通；如果有两条边，会形成环。
时间复杂度：O(eloge) 排序，并集查找如果用启发式合并，也是O(nlogn)。

按点加

点分为两个点集S和T，S集只包括任意一个点，T集包括其它点。n1 ∈ \in ∈S,n2 ∈ \in ∈T ，寻找最短的 n 1 ↔ n 2 n1 \leftrightarrow n2 n1↔n2。
将n2加到S, n 1 ↔ n 2 n1 \leftrightarrow n2 n1↔n2 加到最小生成树。更新T中各点到S的最短距离，只需要更新T中各点到n2的距离。
证明:
当前S Ｔ不连通，如果不选择 n 1 ↔ n 2 n1 \leftrightarrow n2 n1↔n2 ,只能选择更长的边。
时间复杂度： O(nn)

题解

删除某条边会，最小生成树不存在或变大，是关键边。
把某条边加到最小生成树后，余下的边继续生成最小关键树，权值不变是伪关键边。

封装库

class CUnionFindMST
{
public:CUnionFindMST(const int iNodeSize) :m_uf(iNodeSize){}void AddEdge(const int iNode1, const int iNode2, int iWeight){if (m_uf.IsConnect(iNode1, iNode2)){return;}m_iMST += iWeight;m_uf.Union(iNode1, iNode2);}void AddEdge(const vector<int>& v){AddEdge(v[0], v[1], v[2]);}int MST(){if (m_uf.GetConnetRegionCount() > 1){return -1;}return m_iMST;}
private:int m_iMST = 0;CUnionFind m_uf;
};class CNearestMST
{
public:CNearestMST(const int iNodeSize) :m_bDo(iNodeSize), m_vDis(iNodeSize, INT_MAX), m_vNeiTable(iNodeSize){}void Init(const vector<vector<int>>& edges){for (const auto& v : edges){Add(v);}}void Add(const vector<int>& v){m_vNeiTable[v[0]].emplace_back(v[1], v[2]);m_vNeiTable[v[1]].emplace_back(v[0], v[2]);}int MST(int start){int next = start;while ((next = AddNode(next)) >= 0);return m_iMST;}int MST(int iNode1, int iNode2, int iWeight){m_bDo[iNode1] = true;for (const auto& it : m_vNeiTable[iNode1]){if (m_bDo[it.first]){continue;}m_vDis[it.first] = min(m_vDis[it.first], (long long)it.second);}m_iMST = iWeight;int next = iNode2;while ((next = AddNode(next)) >= 0);return m_iMST;}private:int AddNode(int iCur){m_bDo[iCur] = true;for (const auto& it : m_vNeiTable[iCur]){if (m_bDo[it.first]){continue;}m_vDis[it.first] = min(m_vDis[it.first], (long long)it.second);}int iMinIndex = -1;for (int i = 0; i < m_vDis.size(); i++){if (m_bDo[i]){continue;}if ((-1 == iMinIndex) || (m_vDis[i] < m_vDis[iMinIndex])){iMinIndex = i;}}if (-1 != iMinIndex){if (INT_MAX == m_vDis[iMinIndex]){m_iMST = -1;return -1;}m_iMST += m_vDis[iMinIndex];}return iMinIndex;}vector<bool> m_bDo;vector<long long> m_vDis;vector < vector<std::pair<int, int>>> m_vNeiTable;long long m_iMST = 0;
};

代码

class Solution {
public:vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {m_c = edges.size();vector<int> indexs;for (int i = 0; i < m_c; i++){indexs.emplace_back(i);}std::sort(indexs.begin(), indexs.end(), [&](const int& i1, const int& i2){return edges[i1][2] < edges[i2][2];});int iMST = 0;{CNearestMST mst(n);mst.Init(edges);iMST = mst.MST();}vector<vector<int>> vRet(2);for (int i = 0; i < m_c; i++){//关键边			{auto tmp = edges;tmp.erase(tmp.begin() + indexs[i]);CNearestMST mst1(n);mst1.Init(tmp);const int iMST1 = mst1.MST();if ((-1 == iMST1) || (iMST1 > iMST)){vRet[0].emplace_back(indexs[i]);continue;}}{CUnionFindMST mst2(n);mst2.AddEdge(edges[indexs[i]]);for (int j = 0; j < m_c; j++){if (j == i){continue;}const auto& v = edges[indexs[j]];mst2.AddEdge(v);}const int iMST2 = mst2.MST();if (iMST2 == iMST){vRet[1].emplace_back(indexs[i]);}}}std::sort(vRet[0].begin(), vRet[0].end());std::sort(vRet[1].begin(), vRet[1].end());return vRet;}int m_c;
};

2023年4月版1

class Solution {
public:
vector<vector> findCriticalAndPseudoCriticalEdges(int n, vector<vector>& edges) {
m_c = edges.size();
vector indexs;
for (int i = 0; i < m_c; i++)
{
indexs.emplace_back(i);
}
std::sort(indexs.begin(), indexs.end(), [&](const int& i1, const int& i2 )
{
return edges[i1][2] < edges[i2][2];
});
int iMST = 0;
{
CUnionFindMST mst(n);
for (int i = 0; i < m_c; i++)
{
const auto& v = edges[indexs[i]];
mst.AddEdge(v);
}
iMST = mst.MST();
}
vector<vector> vRet(2);
for (int i = 0; i < m_c; i++)
{
//关键边
{
CUnionFindMST mst1(n);
for (int j = 0; j < m_c; j++)
{
if (j == i)
{
continue;
}
const auto& v = edges[indexs[j]];
mst1.AddEdge(v);
}
const int iMST1 = mst1.MST();
if ((-1 == iMST1) || (iMST1 > iMST))
{
vRet[0].emplace_back(indexs[i]);
continue;
}
}

		{CUnionFindMST mst2(n);mst2.AddEdge(edges[indexs[i]]);for (int j = 0; j < m_c; j++){if (j == i){continue;}const auto& v = edges[indexs[j]];mst2.AddEdge(v);}const int iMST2 = mst2.MST();if (iMST2 == iMST){vRet[1].emplace_back(indexs[i]);}}}return vRet;
}
int m_c;

};

2023年4月版2

class Solution {
public:
vector<vector> findCriticalAndPseudoCriticalEdges(int n, vector<vector>& edges) {
m_c = edges.size();
vector indexs;
for (int i = 0; i < m_c; i++)
{
indexs.emplace_back(i);
}
std::sort(indexs.begin(), indexs.end(), [&](const int& i1, const int& i2)
{
return edges[i1][2] < edges[i2][2];
});
int iMST = 0;
{
CNearestMST mst(n);
mst.Init(edges);
iMST = mst.MST();
}
vector<vector> vRet(2);
for (int i = 0; i < m_c; i++)
{
//关键边
{
auto tmp = edges;
tmp.erase(tmp.begin() + indexs[i]);
CNearestMST mst1(n);
mst1.Init(tmp);
const int iMST1 = mst1.MST();
if ((-1 == iMST1) || (iMST1 > iMST))
{
vRet[0].emplace_back(indexs[i]);
continue;
}
}
{
CUnionFindMST mst2(n);
mst2.AddEdge(edges[indexs[i]]);
for (int j = 0; j < m_c; j++)
{
if (j == i)
{
continue;
}
const auto& v = edges[indexs[j]];
mst2.AddEdge(v);
}
const int iMST2 = mst2.MST();
if (iMST2 == iMST)
{
vRet[1].emplace_back(indexs[i]);
}
}
}
std::sort(vRet[0].begin(), vRet[0].end());
std::sort(vRet[1].begin(), vRet[1].end());
return vRet;
}
int m_c;
};

通过重边、割边判断

class Solution{
public:vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>&edges) {std::map<int, vector<int>> mWeightToEdgeIndexs;for (int i = 0; i < edges.size(); i++){mWeightToEdgeIndexs[edges[i][2]].emplace_back(i);}CUnionFind uf(n);vector<vector<int>> vRet(2);for (const auto& it : mWeightToEdgeIndexs){CNeiBo2 neiBo(n, false, 0);std::unordered_map<int, std::unordered_map<int,int>> mRepeateEdge;for (const auto index : it.second){const int n1 = edges[index][0];const int n2 = edges[index][1];if (uf.IsConnect(n1, n2)){continue;}const int iRegion1 = uf.GetConnectRegionIndex(n1);		const int iRegion2 = uf.GetConnectRegionIndex(n2);neiBo.Add(iRegion1, iRegion2);mRepeateEdge[iRegion1][iRegion2]++;mRepeateEdge[iRegion2][iRegion1]++;}CCutEdge cutEdge(neiBo.m_vNeiB);for (const auto index : it.second){const int n1 = edges[index][0];const int n2 = edges[index][1];if (uf.IsConnect(n1, n2)){continue;}const int iRegion1 = uf.GetConnectRegionIndex(n1);const int iRegion2 = uf.GetConnectRegionIndex(n2);if (mRepeateEdge[iRegion1][iRegion2] > 1){//重边无论是否是环，都不是关键边vRet[1].emplace_back(index);}else if (cutEdge.IsCut(iRegion1,iRegion2) || cutEdge.IsCut(iRegion2, iRegion1)){vRet[0].emplace_back(index);}else{vRet[1].emplace_back(index);}}	for (const auto index : it.second){const int n1 = edges[index][0];const int n2 = edges[index][1];uf.Union(n1, n2);}}return vRet;}
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关

下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

这篇关于【图轮】【 最小生成树】【 并集查找】1489. 找到最小生成树里的关键边和伪关键边的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


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

相关文章

浅析如何使用Swagger生成带权限控制的API文档

浅析如何使用Swagger生成带权限控制的API文档

《浅析如何使用Swagger生成带权限控制的API文档》当涉及到权限控制时,如何生成既安全又详细的API文档就成了一个关键问题,所以这篇文章小编就来和大家好好聊聊如何用Swagger来生成带有... 目录准备工作配置 Swagger权限控制给 API 加上权限注解查看文档注意事项在咱们的开发工作里，API
阅读更多...
Java使用POI-TL和JFreeChart动态生成Word报告

Java使用POI-TL和JFreeChart动态生成Word报告

《Java使用POI-TL和JFreeChart动态生成Word报告》本文介绍了使用POI-TL和JFreeChart生成包含动态数据和图表的Word报告的方法,并分享了实际开发中的踩坑经验,通过代码... 目录前言一、需求背景二、方案分析三、 POI-TL + JFreeChart 实现3.1 Maven
阅读更多...
MybatisGenerator文件生成不出对应文件的问题

MybatisGenerator文件生成不出对应文件的问题

《MybatisGenerator文件生成不出对应文件的问题》本文介绍了使用MybatisGenerator生成文件时遇到的问题及解决方法,主要步骤包括检查目标表是否存在、是否能连接到数据库、配置生成... 目录MyBATisGenerator 文件生成不出对应文件先在项目结构里引入“targetProje
阅读更多...
Python使用qrcode库实现生成二维码的操作指南

Python使用qrcode库实现生成二维码的操作指南

《Python使用qrcode库实现生成二维码的操作指南》二维码是一种广泛使用的二维条码,因其高效的数据存储能力和易于扫描的特点,广泛应用于支付、身份验证、营销推广等领域,Pythonqrcode库是... 目录一、安装 python qrcode 库二、基本使用方法1. 生成简单二维码2. 生成带 Log
阅读更多...
Python使用Pandas库将Excel数据叠加生成新DataFrame的操作指南

Python使用Pandas库将Excel数据叠加生成新DataFrame的操作指南

《Python使用Pandas库将Excel数据叠加生成新DataFrame的操作指南》在日常数据处理工作中,我们经常需要将不同Excel文档中的数据整合到一个新的DataFrame中,以便进行进一步... 目录一、准备工作二、读取Excel文件三、数据叠加四、处理重复数据（可选）五、保存新DataFram
阅读更多...
SpringBoot生成和操作PDF的代码详解

SpringBoot生成和操作PDF的代码详解

《SpringBoot生成和操作PDF的代码详解》本文主要介绍了在SpringBoot项目下,通过代码和操作步骤,详细的介绍了如何操作PDF,希望可以帮助到准备通过JAVA操作PDF的你,项目框架用的... 目录本文简介PDF文件简介代码实现PDF操作基于PDF模板生成，并下载完全基于代码生成，并保存合并P
阅读更多...
详解Java中如何使用JFreeChart生成甘特图

详解Java中如何使用JFreeChart生成甘特图

《详解Java中如何使用JFreeChart生成甘特图》甘特图是一种流行的项目管理工具,用于显示项目的进度和任务分配,在Java开发中,JFreeChart是一个强大的开源图表库,能够生成各种类型的图... 目录引言一、JFreeChart简介二、准备工作三、创建甘特图1. 定义数据集2. 创建甘特图3.
阅读更多...
AI一键生成 PPT

AI一键生成 PPT

AI一键生成 PPT 操作步骤 作为一名打工人，是不是经常需要制作各种PPT来分享我的生活和想法。但是，你们知道，有时候灵感来了，时间却不够用了！😩直到我发现了Kimi AI——一个能够自动生成PPT的神奇助手！🌟 什么是Kimi？ 一款月之暗面科技有限公司开发的AI办公工具，帮助用户快速生成高质量的演示文稿。 无论你是职场人士、学生还是教师，Kimi都能够为你的办公文
阅读更多...
pdfmake生成pdf的使用

pdfmake生成pdf的使用

实际项目中有时会有根据填写的表单数据或者其他格式的数据，将数据自动填充到pdf文件中根据固定模板生成pdf文件的需求 文章目录 利用pdfmake生成pdf文件1.下载安装pdfmake第三方包2.封装生成pdf文件的共用配置3.生成pdf文件的文件模板内容4.调用方法生成pdf 利用pdfmake生成pdf文件 1.下载安装pdfmake第三方包 npm i pdfma
阅读更多...
poj 1258 Agri-Net（最小生成树模板代码）

poj 1258 Agri-Net（最小生成树模板代码）

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码：效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2