cphb icon indicating copy to clipboard operation
cphb copied to clipboard

Improve the performance of the "find" function from the Union-Find Data Structure

Open ZhongxuanWang opened this issue 3 years ago • 1 comments

The old implementation is defective and the program will spend much more time in searching for the root. However with the new recursive implementation, after finding out the root the root index is stored in the starting point, which will reduce the number of paths they will have to go, improving the running time a lot.

ZhongxuanWang avatar Mar 07 '21 13:03 ZhongxuanWang

I think this change implements path compression, which is quite reasonable to have.

I would suggest implementing it using a loop, though. Otherwise, it's totally possible to catch a stack overflow.

apronchenkov avatar Nov 26 '21 22:11 apronchenkov