Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

[内容有误] Tarjan算法求LCA #3927

Closed
1 task
ghost opened this issue Apr 21, 2022 · 5 comments
Closed
1 task

[内容有误] Tarjan算法求LCA #3927

ghost opened this issue Apr 21, 2022 · 5 comments
Labels
Content Bug / 页面内容有误 Something isn't working help wanted / 需要帮助 Extra attention is needed

Comments

@ghost
Copy link

ghost commented Apr 21, 2022

请选择：

  • 我正在着手修复这个问题

我正在访问这个页面

https://oi-wiki.org/graph/lca/#tarjan

我发现页面有这样的问题

image
根据参考文献，需要修改并查集的实现，才能得到$O(1)$的复杂度。并不是只要写带路径压缩的并查集就可以自动得到$O(1)$的复杂度。
@ghost ghost added Content Bug / 页面内容有误 Something isn't working help wanted / 需要帮助 Extra attention is needed labels Apr 21, 2022
@welcome
Copy link

welcome bot commented Apr 21, 2022

感谢你对 OI Wiki 的关注！记得在 Issue 中表达清楚自己的意思哦～

@Cat-shao
Copy link
Contributor

Cat-shao commented Apr 29, 2022 •
edited by unfurl-links bot

本人找到一个这个 https://ljt12138.blog.uoj.ac/blog/4874 ，不知道有没有帮助。

@Great-designer
Copy link
Contributor

作为#1567 的延续

@Cat-shao
Copy link
Contributor

@Great-designer 求 lca 算法不是 tarjan 最早提出的。

@psz2007
Copy link
Contributor

psz2007 commented May 19, 2023

现在才看到这个，在 #4431 大概已经解决了，应该可以 close 了

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
Content Bug / 页面内容有误 Something isn't working help wanted / 需要帮助 Extra attention is needed
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
4 participants
@Cat-shao @Tiphereth-A @Great-designer @psz2007