数据结构-并查集专题(1)

一、前言

因为要开始准备年底的校赛和明年年初的ACM、蓝桥杯、天梯赛,于是开始按专题梳理一下对应的知识点,先从简单入门又值得记录的内容开始,并查集首当其冲。

二、我的模板

虽然说是借用了jiangly鸽鸽的板子,但是自己也小做修改了部分(命名啥的,大体内容并没有修改,jiangly鸽鸽yyds)

#include <bits/stdc++.h>

struct DisjointSet {
    int _n;
    std::vector<int> _fa,_size;
    DisjointSet(){}
    DisjointSet(int n){
        init(n);
    }
    void init(int n) {
        _fa.resize(n);
        std::iota(_fa.begin(),_fa.end(),0);
        _size.assign(n,1);
    }
    int find(int x) {
        if(x!=_fa[x]) {
            _fa[x] = find(_fa[x]);
        }
        return _fa[x];
    }
    bool same(int x,int y) {
        return find(x)==find(y);
    }
    bool merge(int x,int y) {
        int fx = find(x);
        int fy = find(y);
        if(fx!=fy) {
            _size[fx]+=_size[fy];
            _fa[fy] = fx;
            return true;
        }
        return false;
    }
};

三、并查集介绍

并查集(disjoint set),英文直译过来是不相交的集合。我们中文取名成并查集,是因为这类集合主要具有两个操作:并和查,并即合并两个集合,查即查询集合的某些信息。

3.1 并

如果有学习过树的知识,那么理解并查集就比较轻松了。“并”操作类似于将森林(两棵树)转化为一棵树,我们只需要让其中一个并查集的根节点的父亲结点指向另外一个并查集的根节点即可。当然选择的时候,我们倾向于让深度小的树的根节点指向深度大的树的根节点。不过后续用上路径压缩后,谁指向谁基本没有什么太大的影响。实际写代码中,我们主要的操作就是对一个并查集的根节点进行修改

3.2 查

1.查询某个节点的根节点 2.查询两个节点是否处于同一个并查集中 3.查询一共有几个并查集 4.查询节点数量最多的并查集和它的节点数量 5.查询节点位于自身并查集的深度

3.3 初始化

在没有进行任何合并前,一个并查集的根节点应该为它自身(切记写代码的时候不要忘记并查集的初始化,当然如果用我的模板的话就不会忘记初始化,构造函数已经写好初始化了)

3.4 路径压缩

正常来说,并查集合并的时间复杂度为O(1),而查询的最坏时间复杂度为O(n),常见的最坏情况就是只有左子树或者只有右子树的一棵树的查询。而如果我们在查询时顺带将查询路径上的结点的父节点属性顺带修改为真正的根节点,那么综合下来,时间复杂度将会被均摊成O(logn),这是一个非常优秀的优化。

四、专题训练

以我学校OJ题目展开训练

4.1 题目总览

4.2 1520: 数据结构-并查集-家庭问题

思路

这道题是很典型的用并查集做的题目,先对并查集进行初始化,我们直接把有关系的两人进行合并,如果已经处于同一个并查集中则不做操作。后续题目需要我们查询的是并查集的数量以及并查集中最大的节点数量

参考代码

前面都是并查集模板,注意构造并查集的时候至少把节点数+1(因为用于实现的vetcor下标从0开始,大部分题目的下标是从1开始的),最后查询的时候利用set进行排序输出即可

#include <bits/stdc++.h>
using i64 = long long;

struct DisjointSet {
    int _n;
    std::vector<int> _fa,_size;
    DisjointSet(){}
    DisjointSet(int n){
        init(n);
    }
    void init(int n) {
        _fa.resize(n);
        std::iota(_fa.begin(),_fa.end(),0);
        _size.assign(n,1);
    }
    int find(int x) {
        if(x!=_fa[x]) _fa[x] = find(_fa[x]);
        return _fa[x];
    }
    bool same(int x,int y) {
        return find(x)==find(y);
    }
    bool merge(int x,int y) {
        int fx = find(x);
        int fy = find(y);
        if(fx!=fy) {
            _size[fy]+=_size[fx];
            _fa[fx] = fy;
            return true;
        }
        return false;
    }
};
using pii = std::pair<int,int>;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n,k;
    std::cin >> n >> k;
    DisjointSet disjointSet = DisjointSet(n+1);
    for(int i = 0;i<k;i++) {
        int mem1,mem2;std::cin >> mem1 >> mem2;
        disjointSet.merge(mem1,mem2);
    }
    std::set<pii> st;
    for(int i = 1;i<=n;i++) {
        int t = disjointSet.find(i);
        st.insert(std::make_pair(disjointSet._size[t],t));
    }
    std::cout << st.size() << ' ' << (*st.rbegin()).first << '\n';

    return 0;
}

4.3 1565: 并查集-团伙

思路

这个题由于enemy的存在,需要多维护一个ene[]数组,ene[]数组初始化为0,如果遇到p等于0的时候,分别判断x和y的ene是否为0,如果为0,则代表他们当前没有enemy,则把ene值设置成对方,即x和y分别属于两个并查集中,如果当前存在ene,那么就把自己合并到他们enemy的并查集中,因为敌人的敌人是朋友。至于p等于1的情况,当做正常并查集的合并来做。最后输出并查集的数量(计算父节点等于自身的节点数量)即可

参考代码

#include <bits/stdc++.h>
using i64 = long long;

struct DisjointSet {
    int _n;
    std::vector<int> _fa,_size;
    DisjointSet(){}
    DisjointSet(int n){
        init(n);
    }
    void init(int n) {
        _fa.resize(n);
        std::iota(_fa.begin(),_fa.end(),0);
        _size.assign(n,1);
    }
    int find(int x) {
        if(x!=_fa[x]) {
            _fa[x] = find(_fa[x]);
        }
        return _fa[x];
    }
    bool same(int x,int y) {
        return find(x)==find(y);
    }
    bool merge(int x,int y) {
        int fx = find(x);
        int fy = find(y);
        if(fx!=fy) {
            _size[fy]+=_size[fx];
            _fa[fx] = fy;
            return true;
        }
        return false;
    }
};

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n,m;
    std::cin >> n >> m;
    DisjointSet disjointSet = DisjointSet(n+1);
    std::vector<int> ene(n+1,0);

    for(int i = 0;i<m;i++) {
        int t,x,y;std::cin >> t >> x >> y;
        if(t) {//enemy
            if(ene[x]) {
                disjointSet.merge(y,ene[x]);
            }else {
                ene[x] = y;
            }
            if(ene[y]) {
                disjointSet.merge(x,ene[y]);
            }else {
                ene[y] = x;
            }
        }else {//friend
            disjointSet.merge(x,y);
        }
    }

    int ans = 0;
    for(int i = 1;i<=n;i++) {
        if(disjointSet.find(i)==i) ++ans;
    }
    std::cout << ans << '\n';

    return 0;
}

4.4 1566: 并查集-打击犯罪

思路

题目有点反直觉,我一开始想着从1到k依次进行判断,断开某个关系后可以使得他们中最大的一个危险程度小于等于n/2,然后后来发现写起来很困难。正难则反,因此我们考虑从n开始循环,跑到1结束,每次循环让这个循环变量i这个节点和它有关系并且大于k的j节点进行合并,然后看看是否有危险程度大于n/2的并查集即可。

参考代码

#include <bits/stdc++.h>
using i64 = long long;

struct DisjointSet {
    int _n;
    std::vector<int> _fa,_size;
    DisjointSet(){}
    DisjointSet(int n){
        init(n);
    }
    void init(int n) {
        _fa.resize(n);
        std::iota(_fa.begin(),_fa.end(),0);
        _size.assign(n,1);
    }
    int find(int x) {
        if(x!=_fa[x]) {
            _fa[x] = find(_fa[x]);
        }
        return _fa[x];
    }
    bool same(int x,int y) {
        return find(x)==find(y);
    }
    bool merge(int x,int y) {
        int fx = find(x);
        int fy = find(y);
        if(fx!=fy) {
            _size[fx]+=_size[fy];
            _fa[fy] = fx;
            return true;
        }
        return false;
    }
};

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n;std::cin >> n;
    std::vector<std::vector<int>> edges(n+1,std::vector<int>());
    DisjointSet disjointSet = DisjointSet(n+1);

    for(int i = 0;i<n;i++) {
        int siz;std::cin >> siz;
        for(int j = 0;j<siz;j++) {
            int t;std::cin >> t;
            edges[i+1].emplace_back(t);
        }
    }
    
    for(int k = n;k>=1;k--) {
        for(auto &edge:edges[k]) {
            if(edge>k) {
                disjointSet.merge(k,edge);
            }
        }
        if(disjointSet._size[disjointSet.find(k)]>n/2) {
            std::cout << k << '\n';
            return 0;
        }
    }

    return 0;
}

4.5 1567: 并查集-搭配购买

思路

并查集+01背包,中间对数据的存储搞得我很头疼,用了一堆vector,先把c[]和d[]数组存起来,做了并查集的合并后,再算一个并查集c[]的总和sumc[]以及d[]的总和sumd[],然后把计算好的总和放进real_c[]和real_d[]数组中,再使用一个dp[]数组做一遍01背包,最后的dp[w]输出即可

参考代码

#include <bits/stdc++.h>
using i64 = long long;

struct DisjointSet {
    int _n;
    std::vector<int> _fa,_size;
    DisjointSet(){}
    DisjointSet(int n){
        init(n);
    }
    void init(int n) {
        _fa.resize(n);
        std::iota(_fa.begin(),_fa.end(),0);
        _size.assign(n,1);
    }
    int find(int x) {
        if(x!=_fa[x]) {
            _fa[x] = find(_fa[x]);
        }
        return _fa[x];
    }
    bool same(int x,int y) {
        return find(x)==find(y);
    }
    bool merge(int x,int y) {
        int fx = find(x);
        int fy = find(y);
        if(fx!=fy) {
            _size[fx]+=_size[fy];
            _fa[fy] = fx;
            return true;
        }
        return false;
    }
};
using pii = std::pair<int,int>;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n,m,w;
    std::cin >> n >> m >> w;
    std::vector<int> c,d;

    for(int i = 0;i<n;i++) {
        int tmpc,tmpd;
        std::cin >> tmpc >> tmpd;
        c.emplace_back(tmpc);
        d.emplace_back(tmpd);
    }

    DisjointSet disjointSet = DisjointSet(n+1);
    for(int i = 0;i<m;i++) {
        int x,y;std::cin >> x >> y;
        disjointSet.merge(x,y);
    }

    std::vector<int> sumc(n+1,0),sumd(n+1,0);
    for(int i = 1;i<=n;i++) {
        int t = disjointSet.find(i);
        sumc[t] += c[i-1];
        sumd[t] += d[i-1];
    }

    std::vector<int> real_c,real_d;
    for(int i = 1;i<=n;i++) {
        if(sumc[i]!=0) {
            real_c.emplace_back(sumc[i]);
            real_d.emplace_back(sumd[i]);
        }
    }

    std::vector<int> dp(w+1,0);

    for(int i = 0;i<real_c.size();i++) {
        for(int j = w;j>=real_c[i];j--) {
            dp[j] = std::max(dp[j],dp[j-real_c[i]]+real_d[i]);
        }
    }
    std::cout << dp[w] << '\n';

    return 0;
}

五、后记

剩下的题目及并查集的进一步运用(求最小生成树的Kruskal算法)见后续的(2)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/912795.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【dvwa靶场:XSS系列】XSS (Stored)低-中-高级别,通关啦

更改name的文本数量限制大小&#xff0c; 其他我们只在name中进行操作 【除了低级可以在message中进行操作】 一、低级low <script>alert("假客套")</script> 二、中级middle 过滤了小写&#xff0c;咱们可以大写 <Script>alert("假客套…

【spark面试】spark的shuffle过程

概述 所有的shuffle的过程本质上就是一个task将内存中的数据写入磁盘&#xff0c;然后另一个task将磁盘中的数据读入内存的过程。 对于mapreduce来说&#xff0c;我们将内存中的数据写入磁盘成为maptask&#xff0c;将磁盘中的数据读入内存称为reducetask。 而对于spark来说&…

MySQL —— Innodb 索引数据结构

文章目录 不用平衡二叉树或红黑树作为索引B树适合作为索引比B树更适合作为索引的结构——B树总结 MySQL 使用 B树索引数据结构&#xff08;因为默认使用 innodb 存储引擎&#xff09; B树&#xff1a;有序数组 平衡多叉树&#xff1b;B树&#xff1a;有序数组链表 平衡多叉树…

shell中执行hive指令以及hive中执行shell和hdfs指令语法

0. 简介 主要介绍了三种环境命令执行语法&#xff1a; shell中执行hive指令hive中执行shell指令hive中执行hdfs指令 1. shell中执行hive指令 语法&#xff1a;hive [-hiveconf xy]* [<-i filename>]* [<-f filename> | <-e query-string>] [-S] 说明&…

MySQL系列之如何在Linux只安装客户端

导览 前言Q&#xff1a;如何安装一个Linux环境下的MySQL客户端一、准备文件1. 确认Server版本2. 选择Client安装文件 二、下载并安装1. 下载1.1 寻找文件1.2 文件说明 2. 安装2.1 上传至Linux服务器2.2 执行安装 三、连接验证1. 确认远程授权2. 建立远程连接 结语精彩回放 前言…

C++20 概念与约束(3)—— 约束的进阶用法

1、再谈约束主句与从句 上一篇文章中提到过约束可以无限嵌套。末尾也提到不考虑嵌套约束的情况下&#xff0c;模板因为 SFINAE 规则的存在&#xff0c;其中 requires 子句只要存在返回值&#xff0c;只有可能是 true 这一种结果。在非模板中&#xff0c;如果 requires 子句中的…

进程启动时,main 函数是如何被找到的?

Linux中一个进程是如何被启动起来的&#xff1f; 一、进程是怎么启动的&#xff1f;二、进程内存空间分段三、进程的入口函数四、总结 一、进程是怎么启动的&#xff1f; 当一个程序被执行时&#xff0c;怎么看出进程的运行呢&#xff1f;一个进程是怎么启动的&#xff1f;为什…

关于 el-table 的合计行问题

目录 一.自定义合计行 二.合计行不展示&#xff0c;只有缩放/变大窗口或者F12弹出后台时才展示 三.合计行出现了表格滚动条下方 四.合计行整体样式的修改 五.合计行单元格样式修改 1.css 2.jsx方式 六.合计行单元格合并 一.自定义合计行 通过 show-summary 属性开启合计…

十三:java web(5)-- Spring数据持久层

目录 Spring 数据持久层 1. Spring 与 JDBC 1.1 使用 Spring 管理数据库连接 1.1.2 Apache Commons DBCP 基于配置文件xml 使用 1.1.3 Apache Commons DBCP 基于配置类使用 1.1.4 HikariCP 基于配置文件xml 使用 推荐使用 Spring Boot 默认连接池 1.1.5 HikariCP 基于配置…

初学者指南:用例图——开启您的软件工程之旅

目录 背景&#xff1a; 基本组成&#xff1a; 关联&#xff08;Assciation&#xff09;&#xff1a; 包含&#xff08;Include&#xff09;&#xff1a; 扩展&#xff08;Extend&#xff09;&#xff1a; 泛化&#xff08;Inheritance&#xff09;&#xff1a; 完整银行…

基于单片机洗衣机控制器的设计(论文+源码)

1需求分析 在智能洗衣机系统设计中&#xff0c;考虑到洗衣机在实际应用过程中&#xff0c;需要满足用户对于不同衣物清洁、消毒的应用要求&#xff0c;对设计功能进行分析&#xff0c;具体如下&#xff1a; 通过按键实现洗衣机不同工作模式的切换&#xff0c;包括标准模式&am…

qt QFontDialog详解

1、概述 QFontDialog 是 Qt 框架中的一个对话框类&#xff0c;用于选择字体。它提供了一个可视化的界面&#xff0c;允许用户选择所需的字体以及相关的属性&#xff0c;如字体样式、大小、粗细等。用户可以通过对话框中的选项进行选择&#xff0c;并实时预览所选字体的效果。Q…

Python学习从0到1 day27 第三阶段 Spark ③ 数据计算 Ⅱ

目录 一、Filter方法 功能 语法 代码 总结 filter算子 二、distinct方法 功能 语法 代码 总结 distinct算子 三、SortBy方法 功能 语法 代码 总结 sortBy算子 四、数据计算练习 需求&#xff1a; 解答 总结 去重函数&#xff1a; 过滤函数&#xff1a; 转换函数&#xff1a; 排…

今天,智谱「新清影」上线,率先进入有声视频生成时代!还要继续开源宠粉

来&#xff0c;你先把手机音量打开&#xff0c;然后去“听”下面一段视频&#xff1a; 你是不是一脸懵逼&#xff1f;不知道我想表达什么&#xff1f; 视频是AI生成的并不奇怪&#xff0c;但你可能没法相信&#xff0c;这个视频的音效&#xff0c;也是AI生成的。 火车鸣笛 你…

「Mac畅玩鸿蒙与硬件31」UI互动应用篇8 - 自定义评分星级组件

本篇将带你实现一个自定义评分星级组件&#xff0c;用户可以通过点击星星进行评分&#xff0c;并实时显示评分结果。为了让界面更具吸引力&#xff0c;我们还将添加一只小猫图片作为评分的背景装饰。 关键词 UI互动应用评分系统自定义星级组件状态管理用户交互 一、功能说明 …

pdf转excel;pdf中表格提取

一、问题描述 在工作中或多或少会遇到&#xff1a;需要将某份pdf中的表格数据提取出来&#xff0c;以便能够“修改使用”数据 可将pdf中的表格提取出来&#xff0c;解决办法还有点复杂 尤其涉及“pdf中表格不是标准的单元格”的时候&#xff0c;提取数据到excel不太容易 比…

IT架构管理

目录 总则 IT架构管理目的 明确组织与职责 IT架构管理旨在桥接技术实施与业务需求之间的鸿沟&#xff0c;通过深入理解业务战略和技术能力&#xff0c;推动技术创新以支持业务增长&#xff0c;实现技术投资的最大价值。 设定目标与范围 IT架构管理的首要目的是确立清晰的组织…

小红书图文矩阵的运营策略与引流技巧解析

内容概要 小红书图文矩阵是一种高效的内容运营方式&#xff0c;能够帮助品牌在竞争激烈的环境中脱颖而出。通过构建矩阵账号&#xff0c;品牌可以实现多维度的内容覆盖&#xff0c;创造出丰富而立体的用户体验。为什么要做图文矩阵&#xff1f;首先&#xff0c;这种方式能够提…

python中常见的8种数据结构之一元组

元组&#xff08;tuple&#xff09;是Python中常见的数据结构之一&#xff0c;它是一个有序、不可变的序列。元组使用圆括号来表示&#xff0c;可以包含任意类型的元素&#xff0c;包括数字、字符串、列表等。元组的元素可以通过索引访问&#xff0c;但是不能修改。 下面是一些…

计算机毕业设计Python+大模型动漫推荐系统 动漫视频推荐系统 机器学习 协同过滤推荐算法 bilibili动漫爬虫 数据可视化 数据分析 大数据毕业设计

作者简介&#xff1a;Java领域优质创作者、CSDN博客专家 、CSDN内容合伙人、掘金特邀作者、阿里云博客专家、51CTO特邀作者、多年架构师设计经验、多年校企合作经验&#xff0c;被多个学校常年聘为校外企业导师&#xff0c;指导学生毕业设计并参与学生毕业答辩指导&#xff0c;…