2024-02-24:给你一个 n 个点

2024-02-24:用go语言,给你一个 n 个点的带权无向连通图,节点编号为 0 到 n-1,
同时还有一个数组 edges ,其中 edges[i] = [fromi, toi, weighti],
表示在 fromi 和 toi 节点之间有一条带权无向边,
最小生成树 (MST) 是给定图中边的一个子集,
它连接了所有节点且没有环,而且这些边的权值和最小。
请你找到给定图中最小生成树的所有关键边和伪关键边。
如果从图中删去某条边,会导致最小生成树的权值和增加,那么我们就说它是一条关键边,
伪关键边则是可能会出现在某些最小生成树中但不会出现在所有最小生成树中的边。
请注意,你可以分别以任意顺序返回关键边的下标和伪关键边的下标。
输入: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]]。
#福大大架构师每日一题#
#Go语言#
2024-02-24
在牛客打卡943天,今天也很努力鸭!
全部评论

相关推荐

无情咸鱼王的秋招日记之薛定谔的Offer:好拒信,偷了,希望有机会用到
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务