文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题找到最小生成树里的关键边和伪关键边出处1489. 找到最小生成树里的关键边和伪关键边难度8 级题目描述要求给定一个n \texttt{n}n个点的带权无向连通图顶点编号为0 \texttt{0}0到n − 1 \texttt{n} - \texttt{1}n−1以及一个数组edges \texttt{edges}edges其中edges[i] [a i , b i , weight i ] \texttt{edges[i] [a}_\texttt{i}\texttt{, b}_\texttt{i}\texttt{, weight}_\texttt{i}\texttt{]}edges[i] [ai​, bi​, weighti​]表示在顶点a i \texttt{a}_\texttt{i}ai​和b i \texttt{b}_\texttt{i}bi​之间有一条带权无向边。最小生成树是给定图中边的一个子集它连接了所有顶点且没有环而且这些边的权值和最小。找到图中最小生成树的所有关键边和伪关键边。如果从图中删去某条边会导致最小生成树的权值和增加那么这条边是关键边。伪关键边则是可能会出现在某些最小生成树中但不会出现在所有最小生成树中的边。可以分别按任意顺序返回关键边的下标和伪关键边的下标。示例示例 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]] \texttt{n 5, edges [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]}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]] \texttt{[[0,1],[2,3,4,5]]}[[0,1],[2,3,4,5]]解释上图描述了给定图。下图是所有的最小生成树。第0 \texttt{0}0条边和第1 \texttt{1}1条边出现在了所有最小生成树中所以它们是关键边将这两个下标作为输出的第一个列表。边2 \texttt{2}2、3 \texttt{3}3、4 \texttt{4}4和5 \texttt{5}5只在部分最小生成树中出现所以它们是伪关键边将它们作为输出的第二个列表。示例 2输入n 4, edges [[0,1,1],[1,2,1],[2,3,1],[0,3,1]] \texttt{n 4, edges [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]}n 4, edges [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]输出[[],[0,1,2,3]] \texttt{[[],[0,1,2,3]]}[[],[0,1,2,3]]解释由于4 \texttt{4}4条边都有相同的权值任选其中的3 \texttt{3}3条边都可以形成最小生成树。所以4 \texttt{4}4条边都是伪关键边。数据范围2 ≤ n ≤ 100 \texttt{2} \le \texttt{n} \le \texttt{100}2≤n≤1001 ≤ edges.length ≤ min(200, n × (n − 1) 2 \texttt{1} \le \texttt{edges.length} \le \texttt{min(200, }\dfrac{\texttt{n} \times \texttt{(n} - \texttt{1)}}{\texttt{2}}1≤edges.length≤min(200,2n×(n−1)​edges[i].length 3 \texttt{edges[i].length} \texttt{3}edges[i].length30 ≤ a i b i n \texttt{0} \le \texttt{a}_\texttt{i} \texttt{b}_\texttt{i} \texttt{n}0≤ai​bi​n1 ≤ weight i ≤ 1000 \texttt{1} \le \texttt{weight}_\texttt{i} \le \texttt{1000}1≤weighti​≤1000所有(a i , b i ) \texttt{(a}_\texttt{i}\texttt{, b}_\texttt{i}\texttt{)}(ai​, bi​)数对各不相同解法思路和算法这道题要求判断图中的每条边是否为最小生成树的关键边和伪关键边需要首先计算原始图中的最小生成树的权重之和然后依次遍历每条边判断每条边是否为关键边和伪关键边。由于这道题需要遍历每条边做判断因此适合使用 Kruskal 算法。Kruskal 算法的做法是按照权重递增的顺序依次遍历每条边判断每条边是否可以作为最小生成树中的一条边。由于这道题需要维护原始数组edges \textit{edges}edges中的每条边的下标因此需要新建数组edgesIndices \textit{edgesIndices}edgesIndices记录每条边和每条边的下标然后对数组edgesIndices \textit{edgesIndices}edgesIndices按照权重升序排序之后每次计算最小生成树都可以使用数组edgesIndices \textit{edgesIndices}edgesIndices的信息。首先计算原始图中的最小生成树的权重之和记为mstWeight \textit{mstWeight}mstWeight然后依次遍历每条边判断每条边是否为关键边和伪关键边。当遍历到排序后的第i ii条边时记边下标为index \textit{index}index执行如下操作。将第i ii条边移除。如果移除第i ii条边之后的图中的最小生成树的权重之和大于mstWeight \textit{mstWeight}mstWeight则移除第i ii条边会导致最小生成树的权重之和增加因此第i ii条边是关键边。如果移除第i ii条边之后的图不连通则将移除第i ii条边之后的图中的最小生成树的权重之和记为∞ \infty∞同样大于mstWeight \textit{mstWeight}mstWeight因此第i ii条边是关键边。如果第i ii条边是关键边则将index \textit{index}index添加到关键边下标列表中。如果移除第i ii条边之后的图中的最小生成树的权重之和等于mstWeight \textit{mstWeight}mstWeight则第i ii条边一定不是关键边可能是伪关键边如果存在一个最小生成树包含第i ii条边则第i ii条边是伪关键边。判断第i ii条边是否为伪关键边的做法是将第i ii条边作为最小生成树中的初始边然后构造最小生成树如果构造出的最小生成树的权重之和等于mstWeight \textit{mstWeight}mstWeight则第i ii条边是伪关键边否则第i ii条边不是伪关键边。如果第i ii条边是伪关键边则将index \textit{index}index添加到伪关键边下标列表中。将第i ii条边恢复。遍历结束之后即可得到图中最小生成树的所有关键边和伪关键边。代码classSolution{publicListListIntegerfindCriticalAndPseudoCriticalEdges(intn,int[][]edges){ListIntegercriticalEdgesnewArrayListInteger();ListIntegerpseudoCriticalEdgesnewArrayListInteger();intmedges.length;int[][]edgesIndicesnewint[m][4];for(inti0;im;i){System.arraycopy(edges[i],0,edgesIndices[i],0,3);edgesIndices[i][3]i;}Arrays.sort(edgesIndices,(a,b)-a[2]-b[2]);boolean[]includednewboolean[m];Arrays.fill(included,true);intmstWeightkruskal(n,edgesIndices,included,-1);for(inti0;im;i){intindexedgesIndices[i][3];included[i]false;if(kruskal(n,edgesIndices,included,-1)mstWeight){criticalEdges.add(index);}elseif(kruskal(n,edgesIndices,included,i)mstWeight){pseudoCriticalEdges.add(index);}included[i]true;}ListListIntegercriticalAndPseudoCriticalEdgesnewArrayListListInteger();criticalAndPseudoCriticalEdges.add(criticalEdges);criticalAndPseudoCriticalEdges.add(pseudoCriticalEdges);returncriticalAndPseudoCriticalEdges;}publicintkruskal(intn,int[][]edgesIndices,boolean[]included,intstartEdgeIndex){intmstWeight0;UnionFindufnewUnionFind(n);if(startEdgeIndex0){int[]startEdgeedgesIndices[startEdgeIndex];mstWeightstartEdge[2];uf.union(startEdge[0],startEdge[1]);}intmedgesIndices.length;for(inti0;imuf.getCount()1;i){if(!included[i]){continue;}int[]edgeedgesIndices[i];intvertex0edge[0],vertex1edge[1],weightedge[2];if(uf.find(vertex0)!uf.find(vertex1)){mstWeightweight;uf.union(vertex0,vertex1);}}returnuf.getCount()1?mstWeight:Integer.MAX_VALUE;}}classUnionFind{privateint[]parent;privateint[]rank;privateintcount;publicUnionFind(intn){parentnewint[n];for(inti0;in;i){parent[i]i;}ranknewint[n];this.countn;}publicvoidunion(intx,inty){introotxfind(x);introotyfind(y);if(rootx!rooty){if(rank[rootx]rank[rooty]){parent[rooty]rootx;}elseif(rank[rootx]rank[rooty]){parent[rootx]rooty;}else{parent[rooty]rootx;rank[rootx];}count--;}}publicintfind(intx){if(parent[x]!x){parent[x]find(parent[x]);}returnparent[x];}publicintgetCount(){returncount;}}复杂度分析时间复杂度O ( n m m 2 log ⁡ m ) O(nm m^2 \log m)O(nmm2logm)其中n nn是图中的顶点数m mm是图中的边数。新建边数组并排序的时间是O ( m log ⁡ m ) O(m \log m)O(mlogm)需要执行 Kruskal 算法m 1 m 1m1次每次 Kruskal 算法的时间复杂度是O ( n m log ⁡ m ) O(n m \log m)O(nmlogm)因此时间复杂度是O ( n m m 2 log ⁡ m ) O(nm m^2 \log m)O(nmm2logm)。空间复杂度O ( n m ) O(n m)O(nm)其中n nn是图中的顶点数m mm是图中的边数。新建边数组的空间是O ( m ) O(m)O(m)并查集的空间是O ( n ) O(n)O(n)Kruskal 算法的辅助空间是O ( m ) O(m)O(m)因此空间复杂度是O ( n m ) O(n m)O(nm)。