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

news/2024/7/15 18:10:35 标签: 算法, c++, leetcode, 最小生成树, 图论, 并集查找, 关键边

本文涉及知识点

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

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++**实现。


http://www.niftyadmin.cn/n/5462027.html

相关文章

关于 UnityEditorWindow

关于 UnityEditorWindow

想要使用UnityEditorWindow作为调试窗口吗&#xff1f; 这样做可以很方便的针对游戏中的重要对象做调试。 但是有一个很不方便的地方&#xff0c;OnGUI 的刷新频率不高&#xff0c;或者说需要鼠标点击之后才会重绘&#xff0c;如何解决这一问题&#xff1f; 可以如下操作&am…
阅读更多...
2-Prometheus监控主机

2-Prometheus监控主机

文章目录 1 介绍2 部署2.1 下载2.2 解压到指定目录2.3 配置进程管理2.4 程序启动参数2.5 启动和监听 3 添加到 Prometheus4. 指标4.1 通过页面查看指标数据4.2 查看都有哪些指标4.3 指标数据规范 5 程序运行参数 1 介绍 Prometheus 使用 node_exporter 服务程序监控 Linux 主机…
阅读更多...
WPF上使用MaterialDesign框架---下载与配置

WPF上使用MaterialDesign框架---下载与配置

一、介绍&#xff1a; Material Design语言的一些重要功能包括 系统字体Roboto的升级版本 &#xff0c;同时颜色更鲜艳&#xff0c;动画效果更突出。杜拉特还简要谈到了新框架的一些变化。谷歌的想法是让谷歌平台上的开发者掌握这个新框架&#xff0c;从而让所有应用就有统一的…
阅读更多...
Appium基础操作元素定位实操入门

Appium基础操作元素定位实操入门

一、基础操作 1、安装和配置：包括安装 Appium 服务器、设置环境变量等。2、启动服务器：使用命令行或相关工具启动 Appium 服务器。3、连接设备或模拟器：将测试设备或模拟器连接到计算机上。4、识别应用程序：指定要测试的应用程序的相关信息，如包名和活动名。上述1~4内容可…
阅读更多...
redis学习-主从复制和哨兵模式

redis学习-主从复制和哨兵模式

目录 1. 主从复制&#xff0c;读写分离 1.1 介绍 1.2 使用命令介绍 1.3 实现 1.4全量复制和增量复制 2.哨兵模式 1. 主从复制&#xff0c;读写分离 1.1 介绍 指的是将一台redis服务器中的数据复制到其他redis服务器&#xff0c;前者称为主机&#xff0c;后者称为从机&#xf…
阅读更多...
基于spark的大数据分析预测地震受灾情况的系统设计

基于spark的大数据分析预测地震受灾情况的系统设计

基于spark的大数据分析预测地震受灾情况的系统设计 在本篇博客中，我们将介绍如何使用Apache Spark框架进行地震受灾情况的预测。我们将结合数据分析、特征工程、模型训练和评估等步骤，最终建立一个预测模型来预测地震造成的破坏程度，同时使用可视化大屏的方式展示数据的分布…
阅读更多...
OpenCV的图像颜色空间转换、缩放、裁剪与旋转

OpenCV的图像颜色空间转换、缩放、裁剪与旋转

OpenCV的图像颜色空间转换 一、引言 在数字图像处理中&#xff0c;颜色空间转换是一个常见的操作。OpenCV作为一个强大的计算机视觉库&#xff0c;提供了丰富的函数来支持颜色空间转换。本文将围绕OpenCV的颜色空间转换展开&#xff0c;帮助读者理解颜色空间的基本概念、转换…
阅读更多...
pytest中文使用文档----10skip和xfail标记

pytest中文使用文档----10skip和xfail标记

1. 跳过测试用例的执行 1.1. pytest.mark.skip装饰器1.2. pytest.skip方法1.3. pytest.mark.skipif装饰器1.4. pytest.importorskip方法1.5. 跳过测试类1.6. 跳过测试模块1.7. 跳过指定文件或目录1.8. 总结 2. 标记用例为预期失败的 2.1. 去使能xfail标记 3. 结合pytest.param方…
阅读更多...
最新文章

Copyright @ 2022~2023