Wx::

并查集

kuangbin 系列专题 5 并查集,题解见 Github,持续更新中

基本思想

个人理解为一种快速集合操作算法,将同类(具有关系)的元素以树的方式组合成一个集合,并通过树根(代表元)来判断不同元素是否属于同一类。

路径压缩

在效率上,并查集的实现需要路径压缩,即在查找根结点(find()操作)时将纵向的树的下方元素都尽量直接连接到树根,以“横向展平”树,使得之后判断某元素的根结点十分快速,以大幅提高效率,此时查找操作的一种写法如下:

// 树以数组的形式存储,节点 i 的父结点表示为 fa[i]
int find(int i) {
    // 首先三目操作符判断当前节点是否为根结点,
    // 若不是的话递归查找其当前父结点的根结点,
    // 同时将结果赋给当前节点父结点,
    // 以在下次查询时快速找到,避免递归
    // (赋值表达式的返回值即等于其右表达式的值)
    return i == fa[i] ? i : fa[i] = find(i);
}

扩展并查集

在以集合的概念操作同类元素的基础上,基于同类元素之间均应具有一定关系,因此某些题目要求指定其之间的关系,而记录这种关系的数据即保存在每个元素节点上,对于这种关系的操作概念上类似向量操作,这种关系在下文中暂称作偏移向量 offset,即 offset[i] 定义为节点 i 指向 fa[i] 的向量,随 find() 更新 fa[i] 时一同更新。此时,查询操作的一种写法如下:

int find(int i) {
    if (fa[i] != i) 
        int p = fa[i];
        fa[i] = find(fa[i]);
        // 注意!在上一步递归 find() 内 i 的父结点 fa[i] 的 offset 已经被改变了,
        // 比如 fa[i] 仍不是根结点时,
        // 因此不能再 find() 之前保存 fa[i] 的 offset 值以后用,
        offset[i] += offset[p];
    }
    return fa[i];
}

基于二进制的集合操作

虽与并查集算法本身关系不大,但一种基于二进制计算的集合相关操作方法也很常用(如某些状态压缩DP题目中)。

子集枚举

for (int s = 0; s < (1 << n); s++) {
	// 判断某元素是否在集合中:
    for(int i = 0; i<n;i++){
        if(s&(1<<i)){
            // 元素 i 在此子集 s 中
        }
    }
}

子集排除元素

s^(1<<i)^(1<<j) // 排除元素 i 和 j

一些性质

  • 若 s' 是 s 的真子集,一定有 s'< s
  • (1<<n)-1 即为全集
  • 子集 A 的补集即为 全集^A
4

评论(0

评论 取消
验证码:
搜索