草庐IT

数据结构与算法 -> 并查集

不见水星记 2023-03-28 原文

一、并查集概念

  • 并查集是一种树形的数据结构，顾名思义，它用于处理一些不交集的合并及查询问题。 它支持两种操作：
    • 查找（Find）：确定某个元素处于哪个子集，单次操作时间复杂度 O(α(n))，即查询元素p和元素q是否属于同一组
    • 合并（Union）：将两个子集合并成一个集合，单次操作时间复杂度 O(α(n))，即合并元素p和元素q所在的组
  • 以下是并查集的常用模板，需要熟练掌握。其中：
    • n 表示节点数
    • p 存储每个点的父节点，初始时每个点的父节点都是自己
    • size 只有当节点是祖宗节点时才有意义，表示祖宗节点所在集合中，点的数量
    • find(x) 函数用于查找 x 所在集合的祖宗节点
    • union(a, b) 函数用于合并 a 和 b 所在的集合

二、并查集模板

1、模板一

// 并查集类。需要维护一个数组和两个方法，find()和union()
class UnionFind {
    constructor(n) {
        this.arr = []
        // 初始默认为每个人是独立圈子，则他的父级就是他自身
        for (let i = 0; i < n; i++) {
            this.arr[i] = i
        }
    }

    // 直到arr[x] === x，停止向上搜索
    find(x) {
        let arr = this.arr
        while (arr[x] !== x) {
            x = arr[x]
        }
        return arr[x]
    }

    // 路径压缩
    union(x, y) {
        let xFather = this.find(x)
        let yFather = this.find(y)
        if (xFather !== yFather) {
            this.arr[xFather] = yFather
        }
    }
}

2、模板二

class UnionFind {
    constructor(size) {
        this.fa = []
        this.size = size
        this.init()
    }
    // 初始化 每个元素的父节点为自身
    init() {
        for(let i = 0; i < this.size; i++) {
            this.fa[i] = i
        }
    }
    // 递归找到根节点，同时进行路径压缩
    find(x) {
        if(x === this.fa[x]) {
            return x
        }
        this.fa[x] = this.find(this.fa[x])
        return this.fa[x]
    }
    // 合并 x, y 直到各自的根节点， 其中一个的指向另一个
    merge(x, y) {
        let fx = this.find(x)
        let fy = this.find(y)
        if(fx !== fy) {
            this.fa[fx] = fy
        }
    }
    // 获取集合数量
    getCount() {
        let count = 0
        for(let i = 0; i < this.size; i++) {
            if(this.fa[i] === i) {
                count++
            }
        }
        return count
    }
}

3、模板三

// 这个并查集使用了一种叫做路径压缩的优化策略，可以有效减少查找操作的时间复杂度
class UnionFind {
    constructor(n) {
        this.count = n;
        this.parent = [];
        this.rank = [];
        for (let i = 0; i < n; i++) {
            this.parent[i] = i;
            this.rank[i] = 1;
        }
    }

    // 查找元素 p 所在的集合编号
    find(p) {
        if (p !== this.parent[p]) {
            this.parent[p] = this.find(this.parent[p]);
        }
        return this.parent[p];
    }

    isConnected(p, q) {
        return this.find(p) === this.find(q);
    }

    // 将元素 p 和元素 q 所在的集合合并
    unionElements(p, q) {
        const pRoot = this.find(p);
        const qRoot = this.find(q);
        if (pRoot === qRoot) {
            return;
        }
        if (this.rank[pRoot] < this.rank[qRoot]) {
            this.parent[pRoot] = qRoot;
        } else if (this.rank[qRoot] < this.rank[pRoot]) {
            this.parent[qRoot] = pRoot;
        } else {
            this.parent[pRoot] = qRoot;
            this.rank[qRoot] += 1;
        }
    }
}

三、力扣例题

四、PDF参考资料

百度网盘：https://pan.baidu.com/s/1FzPwQKEEoSeEWFX-7A104A?pwd=hcfr

ampgtnbspthisfind算法与数据结构

有关数据结构与算法 -> 并查集的更多相关文章

  1. ruby - 使用 ruby​​ 将 HTML 转换为纯文本并维护结构/格式 - 2

    我想将html转换为纯文本。不过，我不想只删除标签，我想智能地保留尽可能多的格式。为插入换行符标签，检测段落并格式化它们等。输入非常简单，通常是格式良好的html(不是整个文档，只是一堆内容，通常没有anchor或图像)。我可以将几个正则表达式放在一起，让我达到80%，但我认为可能有一些现有的解决方案更智能。 最佳答案 首先，不要尝试为此使用正则表达式。很有可能你会想出一个脆弱/脆弱的解决方案，它会随着HTML的变化而崩溃，或者很难管理和维护。您可以使用Nokogiri快速解析HTML并提取文本:require'nokogiri'h

  2. ruby - 解析 RDFa、微数据等的最佳方式是什么，使用统一的模式/词汇(例如 schema.org)存储和显示信息 - 2

    我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i

  3. ruby-on-rails - 如何从 format.xml 中删除 <hash></hash> - 2

    我有一个对象has_many应呈现为xml的子对象。这不是问题。我的问题是我创建了一个Hash包含此数据，就像解析器需要它一样。但是rails自动将整个文件包含在.........我需要摆脱type="array"和我该如何处理？我没有在文档中找到任何内容。 最佳答案 我遇到了同样的问题；这是我的XML:我在用这个:entries.to_xml将散列数据转换为XML，但这会将条目的数据包装到中所以我修改了:entries.to_xml(root:"Contacts")但这仍然将转换后的XML包装在“联系人”中，将我的XML代码修改为

  4. ruby-on-rails - rspec should have_select ('cars' , :options => ['volvo' , 'saab' ] 不工作 - 2

    关闭。这个问题需要detailsorclarity.它目前不接受答案。想改进这个问题吗？通过editingthispost添加细节并澄清问题.关闭8年前。Improvethisquestion在首页我有:汽车:VolvoSaabMercedesAudistatic_pages_spec.rb中的测试代码:it"shouldhavetherightselect"dovisithome_pathit{shouldhave_select('cars',:options=>['volvo','saab','mercedes','audi'])}end响应是rspec./spec/request

  5. ruby - Ruby 有 `Pair` 数据类型吗？ - 2

    有时我需要处理键/值数据。我不喜欢使用数组，因为它们在大小上没有限制(很容易不小心添加超过2个项目，而且您最终需要稍后验证大小)。此外，0和1的索引变成了魔数(MagicNumber)，并且在传达含义方面做得很差(“当我说0时，我的意思是head...”)。散列也不合适，因为可能会不小心添加额外的条目。我写了下面的类来解决这个问题:classPairattr_accessor:head,:taildefinitialize(h,t)@head,@tail=h,tendend它工作得很好并且解决了问题，但我很想知道:Ruby标准库是否已经带有这样一个类？ 最佳

  6. ruby-on-rails - Nokogiri:使用 XPath 搜索 <div> - 2

    我使用Nokogiri(Rubygem)css搜索寻找某些在我的html里面。看起来Nokogiri的css搜索不喜欢正则表达式。我想切换到Nokogiri的xpath搜索，因为这似乎支持搜索字符串中的正则表达式。如何在xpath搜索中实现下面提到的(伪)css搜索？require'rubygems'require'nokogiri'value=Nokogiri::HTML.parse(ABBlaCD3"HTML_END#my_blockisgivenmy_bl="1"#my_eqcorrespondstothisregexmy_eq="\/[0-9]+\/"#FIXMEThefoll

  7. ruby - 是否有用于序列化和反序列化各种格式的对象层次结构的模式？ - 2

    给定一个复杂的对象层次结构，幸运的是它不包含循环引用，我如何实现支持各种格式的序列化？我不是来讨论实际实现的。相反，我正在寻找可能会派上用场的设计模式提示。更准确地说:我正在使用Ruby，我想解析XML和JSON数据以构建复杂的对象层次结构。此外，应该可以将该层次结构序列化为JSON、XML和可能的HTML。我可以为此使用Builder模式吗？在任何提到的情况下，我都有某种结构化数据-无论是在内存中还是文本中-我想用它来构建其他东西。我认为将序列化逻辑与实际业务逻辑分开会很好，这样我以后就可以轻松支持多种XML格式。 最佳答案 我最

  8. ruby - 我如何添加二进制数据来遏制 POST - 2

    我正在尝试使用Curbgem执行以下POST以解析云curl-XPOST\-H"X-Parse-Application-Id:PARSE_APP_ID"\-H"X-Parse-REST-API-Key:PARSE_API_KEY"\-H"Content-Type:image/jpeg"\--data-binary'@myPicture.jpg'\https://api.parse.com/1/files/pic.jpg用这个:curl=Curl::Easy.new("https://api.parse.com/1/files/lion.jpg")curl.multipart_form_

  9. 世界前沿3D开发引擎HOOPS全面讲解——集3D数据读取、3D图形渲染、3D数据发布于一体的全新3D应用开发工具 - 2

    无论您是想搭建桌面端、WEB端或者移动端APP应用，HOOPSPlatform组件都可以为您提供弹性的3D集成架构，同时，由工业领域3D技术专家组成的HOOPS技术团队也能为您提供技术支持服务。如果您的客户期望有一种在多个平台（桌面/WEB/APP，而且某些客户端是“瘦”客户端）快速、方便地将数据接入到3D应用系统的解决方案，并且当访问数据时，在各个平台上的性能和用户体验保持一致，HOOPSPlatform将帮助您完成。利用HOOPSPlatform，您可以开发在任何环境下的3D基础应用架构。HOOPSPlatform可以帮您打造3D创新型产品，HOOPSSDK包含的技术有：快速且准确的CAD

  10. 区块链之加解密算法&数字证书 - 2

    目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非

随机推荐