Iridescent41
Iridescent41
全部文章
分类
未归档(46)
归档
标签
去牛客网
登录
/
注册
ChenJG41
Never Give Up
全部文章
(共1篇)
关于两次dfs/bfs求树的直径反证法思路
刚刚听了jmy讲他的证明方法,大致意思就是树上的任意一点所能到达的最远距离一定会在直径的两个端点上。 但我认为反证法其实来得更快。思路如下: 证明: 反证法。假设已经用两次bfs/dfs求得的直径为\(AB\),且\(AB\)上有一点\(N\)。如果\(AB\)不是这颗树的直径,那么一定存在一条链...
证明
2020-10-04
0
302