Open wzr1005 opened 5 years ago
https://wzr1005.github.io/2019/03/04/%E5%85%B3%E4%BA%8E%E5%9B%BE%E7%9A%84%E7%9B%B4%E5%BE%84/
一道很有意思的算法题，里面有一个证明，还有一些坑： 一个无环连通图的直径可以这样求解：先从任意一点A出发，到达离此结点最远的结点B，，再从B出发所能到达的最深的结点的长度，即是图的直径。 直径不止一条 首尾相同的结点对，可能形成多条路径。 我被第三点卡了很久，后面三个case一直过不去。。这个代码用的是并查集，求最远路径用的是DFS效率没有BFS高，建议用BFS试试。
https://wzr1005.github.io/2019/03/04/%E5%85%B3%E4%BA%8E%E5%9B%BE%E7%9A%84%E7%9B%B4%E5%BE%84/
一道很有意思的算法题，里面有一个证明，还有一些坑： 一个无环连通图的直径可以这样求解：先从任意一点A出发，到达离此结点最远的结点B，，再从B出发所能到达的最深的结点的长度，即是图的直径。 直径不止一条 首尾相同的结点对，可能形成多条路径。 我被第三点卡了很久，后面三个case一直过不去。。这个代码用的是并查集，求最远路径用的是DFS效率没有BFS高，建议用BFS试试。