手机网站asp,安徽建海建设工程有限公司网站,商场设计理念,wordpress缩略图支持外链图给你一个 n 个点的带权无向连通图#xff0c;节点编号为 0 到 n-1 #xff0c;同时还有一个数组 edges #xff0c;其中 edges[i] [fromi, toi, weighti] 表示在 fromi 和 toi 节点之间有一条带权无向边。最小生成树 (MST) 是给定图中边的一个子集#xff0c;它连接了所有…给你一个 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]] 解释上图描述了给定图。 下图是所有的最小生成树。
代码
class Solution {int[] fa;public void init(){for(int i0;ifa.length;i)fa[i]i;}public int find(int x){if(x!fa[x])fa[x]find(fa[x]);return fa[x];}public void union(int x,int y){xfind(x);yfind(y);if(xy) return;fa[x]y;}public ListListInteger findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {fanew int[n];init();int tarn;int min0;int[][] edgenew int[edges.length][4];for(int i0;iedges.length;i){for(int j0;j3;j)edge[i][j]edges[i][j];edge[i][3]i;}Arrays.sort(edge,(o1, o2) - o1[2]-o2[2]);for(int i0;iedge.length;i)//计算最小生成树的权值{if(find(edge[i][0])find(edge[i][1]))continue;union(edge[i][0],edge[i][1]);minedge[i][2];}ListListInteger resnew ArrayList();res.add(new ArrayList());res.add(new ArrayList());for(int i0;iedge.length;i)//遍历所有边{init();tarn;int var0;for(int j0;jedge.length;j)//不加入当前边的情况下计算最小生成树{if(ij||find(edge[j][0])find(edge[j][1])) continue;union(edge[j][0],edge[j][1]); tar--;varedge[j][2];}if(tar!1||varmin)//如果生成的最小生成树权重更大或者无法生成最小生成树消去的边则为关键边{res.get(0).add(edge[i][3]);continue;}init();varedge[i][2];union(edge[i][0],edge[i][1]);//用当前边为开始构造生成树for(int j0;jedge.length;j){if(ij||find(edge[j][0])find(edge[j][1])) continue;union(edge[j][0],edge[j][1]); varedge[j][2];}if(varmin) res.get(1).add(edge[i][3]);//如果当前边构造而成的生成树也等于最小权值则是伪关键边}return res;}
}
