search

PetarV- / Algorithms

Several algorithms and data structures implemented in C++ by me (credited to others where necessary).
MIT License
641 stars 235 forks source link

Lowest Common Ancestor #10

Closed chamow97 closed 6 years ago

chamow97 commented 6 years ago

It would be great if we can add Lowest Common Ancestor Algorithm to the repository.

PetarV- commented 6 years ago

You may find an approach to LCA (in O(log N) per query, with O(N) preprocessing) in the code for HLD: https://github.com/PetarV-/Algorithms/blob/master/Graph%20Algorithms/Heavy-Light%20Decomposition.cpp

I may get around to writing the O(1) variant of LCA at some point, but I never found it necessary to use it in practice.

chamow97 commented 6 years ago

I have a separate file written by me for LCA(O(lg N) per query). Should I include it as a file? Or should I edit your file to add one?

PetarV- commented 6 years ago

I'm not sure what you're asking---my assumption is that you'd like to submit a pull request with a new implementation. This is primarily a personal repository for programming contests, where I typically verify implementations myself by running them on online judge problems. As such, the policy (as outlined in the README file) is that pull requests are generally considered only for correcting bugs in existing implementations.

Furthermore, as I wrote above, the HLD approach already gives you LCA in O(log N), which I have already implemented; therefore I see no need for an additional logarithmic LCA in this repository (especially because HLD is extremely versatile for many things other than LCA, and its code is extremely succinct). In the future, as mentioned, I may try to write the fully-optimised O(1) version, and that one will warrant a separate file.

chamow97 commented 6 years ago

Got it. Thank you.