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

pllk / cphb

Competitive Programmer's Handbook

2.94k stars 354 forks source link

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

Open ZhongxuanWang opened 3 years ago

ZhongxuanWang commented 3 years ago

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.

apronchenkov commented 2 years ago

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.