cphb
cphb copied to clipboard
Improve the performance of the "find" function from the Union-Find Data Structure
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.
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.