y****i
发帖数: 84 | 1 A graph G=(V,E) is a near-tree if it is connected and has at most n+8 edges,
where n=|V|. How to find the minimum spanning tree of G in O(n) time? | g*****u
发帖数: 298 | 2 从最长的边开始，如果它不破坏联通性，就删除，直到剩下n-1条边。大概就这意思吧
？ | kb
发帖数: 73 | 3 find any spanning tree T first. O(n).
Suppose we have m extra edges.
For each edge, put it back into T and find the largest edge on its circle.
After we replaced all these m edges, we are done. Since we have at most 8
extra edges, it is O(n). |
|
