I'm reading Sedgewick & Wayne's Algorithms book, and one of the questions in one of the chapters is the following:
Develop an implementation of Boruvka's algorithm that uses doubly-linked circular lists to represent MST subtrees so that subtrees can be merged and renamed in time bounded by E during each stage (and the union-find data type is therefore not needed).
I'm aware of the standard version of Boruvka's algorithm that uses a union-find data structure to do the merges and check subtree identifiers (there is also an implementation on the book's official website )
But I'm not being able to figure out how to improve the performance of the algorithm by replacing the union-find data structure for subtrees represented by doubly-linked circular lists.
Any ideas? Thanks!