 | Hi
The construction of Prufer is by iteratively delete smallest leaf and
use its neighbor, until only one edge. How to construct Prufer code in
O(nlogn) time?
My basic idea is to adopt the linked list for storage. Use a list to
record whether a node is deleted or not for lazy deletion. Also, maybe
maintain a leaf list could accelerate the algorithm.
Can anybody give me some advice or other optimizations ?
Thanks.
|
|
