longest path in acyclic undirected connected graph

之前在leetcode上做过这题,不过忘记题号了,想请问是否有人知道题号.

解法类似topological sort,计算每个点的degree,然后从最外层(degree 1)的nodes开始搜寻并且update 新的degree.

感谢!

acyclic 还 undirected. mst呗

有个非常巧妙的方法。
1. 任意取一点
2. 深度优先搜索找从那点出发后最长的路径。最后有一个或者多个点都符合这个条件，任意取一个。
3. 从step2中找到的点出发，再做一次深搜，这次找到的最长路径就是该图最长的路径（之一）。