并查集

[Ir1d]

https://oi-wiki.org/ds/dsu/

[NFLSCode]

可以添加压位O(n)的线性序列并查集，类似rmq里面那个

[mahaoming2022]

感谢老师

[Kirigiri123]

够长

[Kirigiri123]

那些实现的代码段都不太懂，有哪位大佬肯讲解吗？explicit是什么呀？

[CoelacanthusHex]

https://en.cppreference.com/w/cpp/language/explicit

[hhc0001]

中文版

[hhc0001]

NOI2011 食物链那道题目可以用常数稍微大一点但是不带边权的并查集解决，方法：

每一个动物开 3 个点，代表这个动物染的三种颜色。

那么，每一次修改时，就会波及到三条边。

判断是否会出现冲突和合并即可。（不需要使用可持久化数据结构）

[congmingyige]

用了启发式合并，一些特殊例子(1->2 ; 2->3 ; n-1->n ; 1->n)，dfs本来用O(n)的栈，变得应该不用O(n)了，猜测是O(nlogn)。还有人用bfs写，以此避免dfs的栈问题

[10-Kirito]

并查集删除的实现是不是存在一些问题？没有考虑是否是叶子结点？老师，这里有点不明白。

[imarkzzz]

不用考虑是不是叶子节点

[imarkzzz]

erase 会执行 find，一步压缩到根, x 的子树都归属到 x 的副本（父亲）

def erase(self, x):
    self.size[self.find(x)] -= 1
    self.pa[x] = x

[Summer-Shen]

可否在这页就显式地介绍一下秩和按秩合并的概念？感谢。

[yxd0379]

文中启发式合并直接使用节点数，按秩合并则是严格按照秩（树高）的大小，秩大的树不动，秩小的树的根指向秩大的树。需要多维护一个rank数组，且union需要修改。

// 按秩合并两个集合
void unionSets(UnionFind *uf, int element1, int element2) {
    int root1 = find(uf, element1);
    int root2 = find(uf, element2);

    if (root1 != root2) {
        if (uf->rank[root1] > uf->rank[root2]) {
            uf->parent[root2] = root1;
        } else if (uf->rank[root1] < uf->rank[root2]) {
            uf->parent[root1] = root2;
        } else {
            uf->parent[root2] = root1;
            uf->rank[root1]++;
        }
    }
}

[Quicksilver-Jacob]

删除某个节点时将父节点设为自身

self.pa[x] = x

在第一次删除后对此节点进行一定操作，这时是否就不能保证它是叶子节点？

[pplam]

启发式合并情况下，是不是也要把 find 改为：

def find(self, x):
    if self.pa[x] != x:
        self.sizes[self.pa[x]] -= self.sizes[x]
        self.pa[x] = self.find(self.pa[x])
    return self.pa[x]

[pplam]

以上都撤回，正确的版本应该是：

def find(self, x):
    if self.pa[x] != x:
            x0 = self.find(self.fa[x])
            fa = self.fa[x]
            if fa != x0:
                self.sizes[fa] -= self.sizes[x]
                self.fa[x] = x0
    return self.pa[x]

😂😂

[RicardoXummm]

路径压缩后 所有叶子节点的size应该都是1了吧，而且维护叶子节点的size好像没有什么意义呜

[pplam]

路径压缩后 所有叶子节点的size应该都是1了吧，而且维护叶子节点的size好像没有什么意义呜

这里主要考虑的是路径压缩时中间节点的size维护，不过你说得也没错，union的时候是root节点union，维护中间节点的size意义不大