The Wikipedia article discusses some applications. One amazing thing I remembered about the algorithm is its running time, which is infinitesimally slower than linear, by which I mean that the growth factor above linear is the inverse Ackermann function! I’ve never studied the analysis but I found the result to be mind boggling.
Thanks, I did look at the Wikipedia page, but the Applications section is pretty difficult to read. The applications it lists are themselves quite abstract problems.
The Wikipedia article discusses some applications. One amazing thing I remembered about the algorithm is its running time, which is infinitesimally slower than linear, by which I mean that the growth factor above linear is the inverse Ackermann function! I’ve never studied the analysis but I found the result to be mind boggling.
https://en.wikipedia.org/wiki/Disjoint-set_data_structure
Thanks, I did look at the Wikipedia page, but the Applications section is pretty difficult to read. The applications it lists are themselves quite abstract problems.