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

相关推荐

06-26 10:08
门头沟学院 C++
北京Golang实习,一个月4700,吃住都不报,公司位置在海淀。请问友友怎么看呢?如果要租房的话有什么建议吗
码农索隆:租房肯定是合租了,剩下的钱,差不多够正常吃饭了,看看能不能学到东西吧
点赞 评论 收藏
分享
程序员饺子:正常 我沟通了200多个 15个要简历 面试2个 全投的成都的小厂。很多看我是27直接不会了😅
点赞 评论 收藏
分享
06-12 10:50
门头沟学院 Java
你的不定积分没加C:我怎么在学院群看到了同样的话
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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