【图轮】【最小生成树】【并集查找】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是边数。

按边加

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

按点加

点分为两个点集S和T，S集只包括任意一个点，T集包括其它点。n1 $\in$ S,n2 $\in$ T ，寻找最短的 $\leftrightarrow n2$ 。
将n2加到S, $\leftrightarrow n2$ 加到最小生成树。更新T中各点到S的最短距离，只需要更新T中各点到n2的距离。
证明:
当前S Ｔ不连通，如果不选择 $\leftrightarrow 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

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