【图轮】【 最小生成树】【 并集查找】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++**实现。

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【C++庖丁解牛】自平衡二叉搜索树--AVL树

【C++庖丁解牛】自平衡二叉搜索树--AVL树

&#x1f341;你好&#xff0c;我是 RO-BERRY &#x1f4d7; 致力于C、C、数据结构、TCP/IP、数据库等等一系列知识 &#x1f384;感谢你的陪伴与支持 &#xff0c;故事既有了开头&#xff0c;就要画上一个完美的句号&#xff0c;让我们一起加油 目录 前言1 AVL树的概念2. AVL…
阅读更多...
【A-006】基于SSH的新闻发布系统（含论文）

【A-006】基于SSH的新闻发布系统（含论文）

【A-006】基于SSH的新闻发布系统&#xff08;含论文&#xff09; 开发环境&#xff1a; Jdk7(8)Tomcat7(8)MySQLIntelliJ IDEA(Eclipse) 数据库&#xff1a; MySQL 技术&#xff1a; SpringStruts2HiberanteJSPJquery 适用于&#xff1a; 课程设计&#xff0c;毕业设计&…
阅读更多...
玩转Django分页器

玩转Django分页器

一、Pagination 分页器编程步骤 View, 导入django.core.paginator.Paginator类&#xff0c;创建Paginator 对象时&#xff0c;输入qs对象&#xff0c;以及每页显示条数。 接收 URL, 从请求参数中读取page数值 &#xff0c;通过 paginator.page(page_num) 返回请求页的page_obj…
阅读更多...
ObjectiveC-05-复杂和特殊数据类型

ObjectiveC-05-复杂和特殊数据类型

这一节中会详细介绍下ObjectiveC中的复杂数据类型&#xff0c;这些类型不太是太归类。但非常有用&#xff0c;有的用于定义变量、有的则是专门用于方法的返回值。 常用的大概有如下这些&#xff1a; 以上这些特殊的数据类型都可用于变量、方法返回值、方法参数使用&#xff0c…
阅读更多...
目标伪类选择器

目标伪类选择器

E:target选择匹配E的所哟元素&#xff0c;且匹配元素被相关url指向 鼠标点击右边京东秒杀跳转到京东秒杀div&#xff0c;并变成黄色 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport&…
阅读更多...
HTML块级元素和内联元素（头部和布局）

HTML块级元素和内联元素（头部和布局）

目录 1.HTML块级和内联标签&#xff1a; 1.块级元素&#xff1a; 2.内联元素: 3.元素嵌套&#xff1a; 4.元素转换&#xff1a; 示例如下: 2.内联框架&#xff1a; 前言&#xff1a; 示例如下: 3.布局&#xff1a; 4.头部标签&#xff1a; 前言&#xff1a; 说明&…
阅读更多...
Java获取当前时间

Java获取当前时间

获取当前的时间 在Java中获取时间和日期使用Date类中的 toString方法 import java.util.Date;public class DateDemo {public static void main(String[] args) {Date date1new Date();System.out.println(date1.toString());} } 进一步格式化时间 SimpleDateFormat 是格式化…
阅读更多...
Netty组件优化之FastThreadLocal

Netty组件优化之FastThreadLocal

ThreadLocal:CSDNhttps://mp.csdn.net/mp_blog/creation/editor/132995427 Netty中的FastThreadLocal是对Java中的FastThreadLocal的优化主要是为了解决ThreadLocal中线性查找 带来的性能下降同时实现快速查找和赋值 FastThreadLocal构建这里的index代表一个编号&#xff0c;从…
阅读更多...
ROS机器人入门第五课：话题通信自定义msg

ROS机器人入门第五课：话题通信自定义msg

文章目录 ROS机器人入门第五课&#xff1a;话题通信自定义msg一、介绍二、流程&#xff08;一&#xff09;定义msg文件&#xff08;二&#xff09;编辑配置文件&#xff08;三&#xff09;编译 三、话题通信自定义msg调用&#xff08;一&#xff09;调用流程0.vscode配置1.发布…
阅读更多...
论文笔记 - ：MonoLSS: Learnable Sample Selection For Monocular 3D Detection

论文笔记 - ：MonoLSS: Learnable Sample Selection For Monocular 3D Detection

论文笔记✍MonoLSS: Learnable Sample Selection For Monocular 3D Detection &#x1f4dc; Abstract &#x1f528; 主流做法限制 &#xff1a; 以前的工作以启发式的方式使用特征来学习 3D 属性&#xff0c;没有考虑到不适当的特征可能会产生不利影响。 &#x1f528; 本…
阅读更多...
基于java+SpringBoot+Vue的网上书城管理系统设计与实现

基于java+SpringBoot+Vue的网上书城管理系统设计与实现

基于javaSpringBootVue的网上书城管理系统设计与实现 开发语言: Java 数据库: MySQL技术: SpringBoot MyBatis工具: IDEA/Eclipse、Navicat、Maven 系统展示 前台展示 后台展示 系统简介 整体功能包含&#xff1a; 网上书城管理系统是一个基于互联网的在线购书平台&#…
阅读更多...
基于springboot实现旅游网站系统项目【项目源码+论文说明】计算机毕业设计

基于springboot实现旅游网站系统项目【项目源码+论文说明】计算机毕业设计

基于springboot实现旅游网站系统演示 摘要 随着科学技术的飞速发展&#xff0c;各行各业都在努力与现代先进技术接轨&#xff0c;通过科技手段提高自身的优势&#xff0c;旅游网站当然也不能排除在外&#xff0c;随着旅游网站的不断成熟&#xff0c;它彻底改变了过去传统的旅游…
阅读更多...
CI/CD实战-jenkins结合ansible 7

CI/CD实战-jenkins结合ansible 7

配置主机环境 在jenkins上断开并删除docker1节点 重新给master添加构建任务 将server3&#xff0c;server4作为测试主机&#xff0c;停掉其上后面的docker 在server2&#xff08;jenkins&#xff09;主机上安装ansible 设置jenkins用户到目标主机的免密 给测试主机创建用户并…
阅读更多...
windows操作系统本地部署开源语言模型ChatGLM3-6b，超详细

windows操作系统本地部署开源语言模型ChatGLM3-6b，超详细

前言 首先感谢智谱AI和清华大学 KEG 实验室联合开源的ChatGLM3对话预训练模型&#xff0c;让我们国人有属于自己的AI聊天机器人。 ChatGLM3-6B 的基础模型 ChatGLM3-6B-Base 采用了更多样的训练数据、更充分的训练步数和更合理的训练策略。在语义、数学、推理、代码、知识等不…
阅读更多...
mysql 用户管理-权限管理

mysql 用户管理-权限管理

学习了用户管理&#xff0c;再学习下权限管理。 3&#xff0c;权限管理 权限管理主要是对登录到MySQL的用户进行权限验证。所有用户的权限都存储在MySQL的权限表中&#xff0c;不合理的权限规划会给MySQL服务器带来安全隐患。数据库管理员要对所有用户的权限进行合理规…
阅读更多...
C++练级之路——C++入门

C++练级之路——C++入门

1、命名空间 在C/C中会出现大量的变量&#xff0c;函数&#xff0c;起名字是一个很大的问题&#xff0c;为了防止命名重复&#xff0c;就出现了命名空间的概念&#xff0c;使用命名空间的目的是对标识符的名称进行本地化&#xff0c;以避免命名冲突和名字污染 #include <st…
阅读更多...
黄金涨是商品牛市的领先信号

黄金涨是商品牛市的领先信号

自2022年11月以来&#xff0c;黄金价格持续上涨&#xff0c;目前已经突破历史新高&#xff0c;历史上黄金上涨&#xff0c;大多是商品全面牛市的领先信号。在2008年Q4、2019年也出现过&#xff0c;黄金比其他商品更强&#xff0c;但随后的2009年和2020年均是商品的全面牛市。同…
阅读更多...
AI副业拆解：使用Suno生成你的专属歌曲

AI副业拆解：使用Suno生成你的专属歌曲

大家好我是在看&#xff0c;记录普通人学习探索AI之路。 今天和大家拆解Suno的定制个性化音乐&#xff0c;Suno应用程序热度非凡&#xff0c;其独特之处在于&#xff0c;用户仅需提供歌词内容与期望的歌曲风格&#xff0c;即可一键生成专属曲目。 Suno的诞生&#xff0c;无疑…
阅读更多...
考研数学｜零基础张宇全年复习规划+资料分享

考研数学｜零基础张宇全年复习规划+资料分享

可以全程张宇老师的高等数学&#xff0c;张宇老师的拿手绝活是 但是其他科目&#xff0c;还有更好的选择&#xff0c;比如线性代数&#xff0c;汤家凤老师还有李永乐老师讲的都不错&#xff0c;概率论&#xff0c;余丙森老师还有方浩老师讲的很好。下面我就讲清楚&#xff0c;…
阅读更多...
FPGA时序优化之Reduce MUXF Mapping

FPGA时序优化之Reduce MUXF Mapping

我们都知道&#xff0c;FPGA中的拥塞有&#xff1a;全局拥塞&#xff0c;短线拥塞和长线拥塞。 今天我们就来看短线拥塞的一种解决方案&#xff1a;Reduce MUXF Mapping。 UltraScale的CLB资源 在介绍Reduce MUXF Mapping&#xff0c;我们需要知道什么是MUXF&#xff0c;这就…
阅读更多...
最新文章

Copyright @ 2022~2023