kuangbin专题5：并查集

知识点

oi-wiki 并查集

两种基本操作：

• 合并（Union）：合并两个元素所属集合（合并对应的树）
• 查询（Find）：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合

进阶操作

• 并查集在经过修改后可以支持单个元素的删除、移动；使用动态开点线段树还可以实现可持久化并查集
• 启发式合并
  • 合并时，选择哪棵树的根节点作为新树的根节点会影响未来操作的复杂度。我们可以将节点较少或深度较小的树连到另一棵，以免发生退化。

复杂度

• 时间复杂度：\(O(\alpha(n))\)，其中\(\alpha(n)\)是阿克曼函数的反函数，可以视为一个很小的常数
• 空间复杂度：\(O(n)\)

模版

struct dsu
{
    vector<size_t> pa, size;

    explicit dsu(size_t size_) : pa(size_), size(size_, 1)
    {
        for (int i = 0; i < size_; i++)
        {
            pa[i] = i;
        }
    }

    size_t find(size_t x)
    {
        return pa[x] == x ? x : pa[x] = find(pa[x]);
    }

    void unite(size_t x, size_t y)
    {
        x = find(x), y = find(y);
        if (x == y)
            return;
        if (size[x] < size[y])
            swap(x, y);
        pa[y] = x;
        size[x] += size[y];
    }

    void erase(size_t x)
    {
        --size[find(x)];
        pa[x] = x;
    }

    void move(size_t x, size_t y)
    {
        size_t fx = find(x), fy = find(y);
        if (fx == fy)
            return;
        pa[x] = fy;
        --size[fx], ++size[fy];
    }
};

应用

• 联通块/连通性相关的图论
• 带权并查集
• 最小生成树：Kruskal
• LCA：Tarjan
• 扩展例题可以看这里

题目记录

前面一些模版题就不放了（我懒了）

POJ - 1182

权值（种类）并查集入门

• find时更新种类，保持与parent的相对关系
• unite时更新种类，保持与root的相对关系
• 一个集合代表其中所有节点互相的相对关系已知

POJ - 1417

权值（种类）并查集+0/1背包，从每个集合中选取一个当divine

• 如果p1 == p2的时候我们无法区分divine和devil
• 如果有多于一种选择方案，我们无法确定
• 再完成背包之后回溯

POJ - 1456

POJ - 1456：贪心的并查集优化

• 贪心将商品价值从大到小排序，每一个商品默认在过期前未使用过的最后一天销售；\(O(n^2)\)
• 并查集优化：使用过的天数与之前的天数合并，这样就可以直接找到“过期前未使用过的最后一天”；\(O(n\alpha(M))\)

POJ - 1733

权值并查集+离散化

• 一个集合代表奇偶性被确定的区间
• unite合并连续/重叠的区间
• 对于已经在同一集合中的区间，检查它的奇偶性是否与集合consistent

POJ - 2492

权值（种类）并查集入门，奇偶性只有两个种类，用异或更新与parent的相对关系即可