并查集

作者: 华雨欣 | 来源:发表于2020-11-10 16:04 被阅读0次

用途

并查集包含合并、查询两种操作,可以接近O(1)的复杂度判断两个元素是否属于同一个集合,通常在最小生成树、查看两个元素是否属于同一个集合(图的连通)、合并集合、集合个数(图的连通分量个数)中均有使用。

模板

int[] p;//并查集

int find(int x){
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

void union(int x, int y){
    int px = find(x), py = find(y);
    p[px] = py;
}

当然还有带权并查集、秩优化等等,就根据题目适当变通即可。
另:个人习惯将合并方法直接拿出来写在调用的位置; 在初始化时 p[i] = i;

相关文章

  • markdown学习

    #并查集 ##并查集的定义 ##并查集的操作

  • 算法模板(四)并查集

    并查集 路径压缩并查集

  • 并查集入门使用

    本文参考自《算法笔记》并查集篇 并查集的定义 什么是并查集?并查集可以理解为是一种维护数据集合的结构。名字中并查集...

  • 并查集练习

    并查集 参考《算法笔记》 三要素:并,查,集。 并差集与一个算法有关,kruskal算法,就可通过并查集实现。 1...

  • 并查集

    并查集 并查集是什么 并查集是一种用来管理元素分组情况的数据结构,并查集可以高效地进行如下操作: 查询元素a和元素...

  • 数据结构与算法(十二)并查集(Union Find)

    本文主要包括以下内容: 并查集的概念 并查集的操作 并查集的实现和优化Quick FindQuick Union基...

  • 并查集

    并查集是什么 并查集是一种用来管理元素分组情况的数据结构。并查集可以高效地进行如下操作。不过需要注意并查集虽然可以...

  • 并查集

    开始时让每个元素构成一个个单元素集合(注意初始化时应使每个元素各成一组)按照一定顺序将属于同一组元素所在的集合合并...

  • 并查集

  • 并查集

    并查集 https://blog.csdn.net/liujian20150808/article/details...

网友评论

      本文标题:并查集

      本文链接:https://www.haomeiwen.com/subject/hyclbktx.html