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天,今天也很努力鸭!
全部评论

相关推荐

牛至超人:哈工大已经很棒了,不需要加括号了,然后咋没有实习经历呢?火速趁寒假整一段实习,导师不让就狠狠肘击
投了多少份简历才上岸
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
01-15 20:52
黑皮白袜臭脚体育生:五宿大战是吧,死去的记忆还在攻击我
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务