feat(ds/dsu.md): 增加了拓展域并查集的内容
- [x] 我已认真阅读贡献指南 (contributing guidelines) 和社区公约 (code of conduct),并遵循了如何参与页及格式手册页的相应规范。
感谢你对 OI Wiki 的关注!记得检查是否遵守了格式规范,听说和项目风格统一的 Pull Request 会更容易被 Merge~
您好,我觉得这个拓展域并查集没有特别突出的理由和并查集本身列为不同的数据结构,更像是一种较为复杂的应用场景。您是否考虑将它添加到并查集页面作为应用之一,而不是单独开一个页面?以及,该页面的带权并查集小节同样引用了食物链这一题目,是不是两者很相似,可以放在一起讨论?仅供参考,谢谢!
您好,我觉得这个拓展域并查集没有特别突出的理由和并查集本身列为不同的数据结构,更像是一种较为复杂的应用场景。您是否考虑将它添加到并查集页面作为应用之一,而不是单独开一个页面?以及,该页面的带权并查集小节同样引用了食物链这一题目,是不是两者很相似,可以放在一起讨论?仅供参考,谢谢!
@c-forrest 很抱歉没有及时看到您的评论。您的评论对我的确有很大的帮助,我将会按照您的意见进行调整。在此表达我最真挚的感谢。
感觉这东西其实就是个二手做法,用处就是能让多个并查集互相连边,处理点被分在多个集合内的情况。(不太准确
例如食物链这道题
我们知道,本题的食物链是一个 A→B→C→A 的三元环。
于是所谓「拓展域并查集」就把一个点拆成 3 份,从而可以处理一个点多种关系的情况。
而「拓展域并查集」的本质其实就是 带权并查集,一篇题解中提到:
边权 $d_x$ 的实质即:三元环上, $x$ 沿有向边走到 $f_x$ 所经过的边数。
「拓展域并查集」就是把一条边权为 $v$ 的边拆成了 $v$ 条边权为 $1$ 的边,他们本质其实是完全相同的,所以「拓展域并查集」就是 带权并查集 的二手做法。感觉只能作为 带权并查集 的一个 trick 来介绍(?)
~~别喷我~~
@Pig-Eat-Earth 但是您把他认为是一个新东西也不是不行
感觉这东西其实就是个二手做法,用处就是能让多个并查集互相连边,处理点被分在多个集合内的情况。(不太准确
例如食物链这道题
我们知道,本题的食物链是一个 A→B→C→A 的三元环。
于是所谓「拓展域并查集」就把一个点拆成 3 份,从而可以处理一个点多种关系的情况。
而「拓展域并查集」的本质其实就是 带权并查集,一篇题解中提到:
边权
d x的实质即:三元环上, x 沿有向边走到
f x所经过的边数。
「拓展域并查集」就是把一条边权为 v 的边拆成了 v 条边权为 1 的边,他们本质其实是完全相同的,所以「拓展域并查集」就是 带权并查集 的二手做法。感觉只能作为 带权并查集 的一个 trick 来介绍(?)
~别喷我~
有道理。
感谢您根据这些评论做出的进一步修改。根据您目前提供的介绍,我建议您将相关内容放到例题一节,通过题解的分析介绍该技巧,而不是单开一小节。目前您在正文中的论述更像是题解中的一部分,而并非一个良定义的具有新的特征的数据结构。相较于带权并查集,它的适用范围也局限于带权并查集维护模意义下边权的场景。所以,通过具体的题目而不是抽象的论述,可能更有助于读者理解该内容。
另外,请尽可能参考其他页面,提供一些风格相近的内容排版,包括使用 example 而非 question 作为例题框,简要介绍题目内容,折叠框内不要放入小节标题,以及中文不要斜体等。这样更有助于 OI Wiki 风格整体统一。
TODO: 整理代码,添加带权并查集的做法
@HeRaNO PTAL, thx!
恭喜!你的 Pull Request 首次被 Merge 了! :smile: