蓝桥杯第十五届抱佛脚(八)并查集

蓝桥杯第十五届抱佛脚(八)并查集

基本概念

并查集是一种数据结构,用于管理一系列不交集的元素集合,并支持两种操作:

查找(Find):

查找操作用于确定某个元素属于哪个集合,这通常通过追溯元素的父节点直到找到代表元素来完成。

合并(Union):

合并操作用于将两个不相交的集合合并为一个。合并可以通过将一个集合的代表元素的父节点指针指向另一个集合的代表元素来完成。

具体实现时,并查集通过一个数组来维护每个元素的父指针,每个集合由一个根元素代表,该根元素的父指针指向自己,表明它是集合的代表。查找操作通过递归或迭代地跟随元素的父指针直到根元素来完成,而合并操作则是将一个集合的根元素的父指针指向另一个集合的根元素。

并查集的两种实现方式

并查集的两种基本实现:quick-findquick-union,这两种方法各有优缺点,并用于解决不相交集合的问题。

quick-find(基于 ID)

quick-find 策略中,每个元素都有一个唯一的标识符,我们称之为 id。在初始化时,每个元素的 id 都是不同的,代表它们各自独立的集合。

操作

  • Find:要判断两个元素是否在同一个集合中,只需比较它们的 id 是否相同。
  • Union:合并两个集合时,我们需要将一个集合中所有元素的 id 全部更新为另一个集合的 id

特点

  • 优点Find 操作非常快,时间复杂度为 O(1)。
  • 缺点Union 操作较慢,因为它需要遍历一个集合中的所有元素来更新 id,时间复杂度为 O(N)。

quick-union(基于 parent)

quick-union 方法使用一个 parent 数组来组织数据,parent[i] 存储的是第 i 个元素的父节点的索引。

操作

  • Find:通过连续追溯父节点直到找到根节点(根节点的特点是 parent[root] == root),这个根节点代表了集合的唯一标识。
  • Union:要合并两个元素所在的集合,只需要将一个集合的根节点的 parent 指向另一个集合的根节点。

特点

  • 优点Union 操作较快,时间复杂度近似为 O(1),只涉及更新一个节点的父节点引用。
  • 缺点Find 操作可能较慢,最坏情况下时间复杂度为 O(N),特别是在树形结构非常深的情况下。

并查集的存储结构

在Java中,一个并查集通常使用一个整数数组来存储。每个索引代表一个特定的元素,而该索引处的值则存储该元素的父节点索引。在并查集的初始状态下,每个元素的父节点索引指向它自己,表示每个元素构成一个单独的集合。这种结构很容易地支持并查集的两个基本操作:查找(Find)和联合(Union)。

以下是一个简单的Java实现,展示了并查集的存储结构和基本操作:

public class UnionFind {
    private int[] parent;  // 存储每个节点的父节点

    // 构造函数,初始化并查集
    public UnionFind(int size) {
        parent = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i; // 初始时,每个元素的父节点指向自己
        }
    }

    // 查找操作,找到元素p的根节点
    public int find(int p) {
        while (p != parent[p]) {
            parent[p] = parent[parent[p]]; // 路径压缩,直接指向根节点
            p = parent[p];
        }
        return p;
    }

    // 联合操作,将元素p和元素q所在的集合合并
    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP != rootQ) {
            parent[rootP] = rootQ; // 将一个集合的根节点指向另一个集合的根节点
        }
    }
}

在这个类中:

  • parent 数组被用作并查集的主要数据结构。
  • UnionFind 构造函数初始化数据结构,设置每个元素的父节点为自己。
  • find 方法实现了路径压缩,使得每次查找操作后,路径上的所有节点都直接连接到根节点。
  • union 方法将两个元素所在的集合合并为一个集合。

按秩合并优化

当并查集的union操作非常频繁,且集合的元素数量很大时,如果不进行优化,通过union操作构造的树可能会非常不平衡,甚至退化成链状结构,这会导致后续的find操作的效率降低。

按秩合并是一种优化union操作的方法,它通过比较两个树的“秩”(通常是树的高度)来决定合并的方向,始终将较低秩的树合并到较高秩的树上,从而避免树的不必要高度增长。

操作步骤

  1. 初始化:对于每个元素,初始化它们的秩(rank)为0,并指定每个元素的父节点为其自身,表示每个元素独立成一个集合。
  2. 合并(Union)操作
    a. 在合并两个元素所在的集合前,首先找到它们各自的根节点(即集合的代表元素)。
    b. 比较两个根节点的秩(代表集合的树的高度)。
    c. 将秩较小的树的根节点指向秩较大的树的根节点。
    d. 如果两棵树的秩相同,选择其中一棵作为代表,将其秩加1。

代码示例

public class UnionFind {
    private int[] parent; // 父节点数组
    private int[] rank;   // 秩数组

    public UnionFind(int size) {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; i++) {
            // 初始化时,每个元素的父节点指向自身
            parent[i] = i;
            // 初始化时,每个元素的秩为0
            rank[i] = 0;
        }
    }

    // 查找元素x的根节点
    public int find(int x) {
        if (x != parent[x]) {
            parent[x] = find(parent[x]); // 路径压缩优化
        }
        return parent[x];
    }

    // 合并元素x和元素y所在的集合
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY; // 将秩较小的树的根指向秩较大的树的根
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                parent[rootY] = rootX; // 如果秩相同,任意合并并更新秩
                rank[rootX]++;
            }
        }
    }

    // 判断两个元素是否在同一个集合中
    public boolean isConnected(int x, int y) {
        return find(x) == find(y);
    }
}

UnionFind 类实现了一个并查集,其中包括了unionfind操作,以及用于检查两个元素是否在同一个集合中的isConnected方法。在union方法中,我们使用了按秩合并的逻辑来优化树的结构。

路径压缩优化

路径压缩主要是针对find操作进行优化的。在没有优化的并查集中,find操作可能需要遍历很长的路径来找到根节点,特别是在union操作导致树高度增加的情况下。

路径压缩在执行find操作时,会将沿途的每个节点直接连接到根节点,这样不仅优化了当前的find操作,也加快了未来对这些节点的find操作。

操作步骤

  1. 查找(Find)操作:在执行查找操作时,递归地访问父节点直到找到根节点。
  2. 路径优化:在递归过程中,将访问过的每个节点直接连接到根节点上,这样可以减少后续操作中访问这些节点时的步骤数。

路径压缩通常和“按秩合并”结合使用,但即使单独使用路径压缩,也能显著提高并查集的效率。

代码示例

public class UnionFind {
    private int[] parent; // 父节点数组

    public UnionFind(int size) {
        parent = new int[size];
        // 初始化,每个节点的父节点是它自己
        for (int i = 0; i < size; i++) {
            parent[i] = i;
        }
    }

    // 查找元素p的根节点
    public int find(int p) {
        // 当我们不是根节点时
        while (p != parent[p]) {
            // 进行路径压缩
            parent[p] = parent[parent[p]];
            // 继续向上查找
            p = parent[p];
        }
        return p;
    }

    // 合并元素p和元素q所在的集合
    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP != rootQ) {
            parent[rootP] = rootQ; // 任意连接两个根节点
        }
    }
}

我们定义了一个UnionFind类,它具有findunion方法。在find方法中,我们实现了路径压缩,通过在查找根节点的过程中更新节点的直接父节点为根节点,来减少后续操作的查找步骤。这种优化可以显著提升并查集的性能,特别是在处理大量findunion操作的时候。

并查集例题

2017年第八届蓝桥杯国赛大学C组真题 合根植物

题目描述:

w 星球的一个种植园,被分成 m×n 个小格子(东西方向 m 行,南北方向 n 列)。每个格子里种了一株合根植物。
这种植物有个特点,它的根可能会沿着南北或东西方向伸展,从而与另一个格子的植物合成为一体。
如果我们告诉你哪些小格子间出现了连根现象,你能说出这个园中一共有多少株合根植物吗?

输入描述:

第一行,两个整数 m,n,用空格分开,表示格子的行数、列数(1 ≤ m,n ≤ 1000)。
接下来一行,一个整数 k (0 ≤ k ≤ 100000 ),表示下面还有 k 行数据。
接下来 k 行,每行两个整数 a,b,表示编号为 a 的小格子和编号为 b 的小格子合根了。
格子的编号一行一行,从上到下,从左到右编号。
比如:5×4 的小格子,编号:
行列
1234
5678
9101112
13141516
17181920

输出描述:

输出植物数量。

输入输出样例:

示例:

输入:

5 4
16
2 3
1 5
5 9
4 8
7 8
9 10
10 11
11 12
10 14
12 16
14 18
17 18
15 19
19 20
9 13
13 17

输出:

5

样例图例如下:

图片描述

解题思路:

在本题中,我们把每个格子视为一个独立的集合,当两个格子“合根”时,我们将它们所在的集合进行合并。最后,计算并查集中独立集合的数量,即为不同的“合根植物”数量。

  1. 初始化并查集:我们创建一个并查集,其中每个格子作为一个独立的集合。在这个并查集中,每个格子最初的父节点是它自己。

  2. 处理合根关系:根据输入的合根关系,我们使用并查集的union方法将这些格子所在的集合进行合并。合并的基本原则是:如果两个格子合根,它们应属于同一个集合。

  3. 计算合根植物的数量:遍历所有格子,计算其父节点是自身的格子数量。这些格子代表了各个不相交集合的根节点,即不同的“合根植物”。

import java.util.Scanner;

class PlantUnionFind {
    private int[] parent; // 存储每个元素的父节点索引

    // 构造方法,初始化并查集
    public PlantUnionFind(int size) {
        parent = new int[size + 1];  // 从1开始编号,因此需要 size + 1 的空间
        for (int i = 1; i <= size; i++) {
            parent[i] = i; // 初始时,每个元素的父节点是它自己
        }
    }

    // 查找元素x的根节点(集合代表)
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩优化
        }
        return parent[x];
    }

    // 合并元素x和y所在的集合
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent[rootX] = rootY; // 将一个集合的根节点指向另一个集合的根节点
        }
    }

    // 计算并查集中独立集合的数量
    public int countPlants() {
        int count = 0;
        for (int i = 1; i < parent.length; i++) {
            if (parent[i] == i) {
                count++; // 如果节点的父节点是它自己,它是一个根节点
            }
        }
        return count;
    }
}

public class Main{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        PlantUnionFind unionFind = new PlantUnionFind(m * n);

        for (int i = 0; i < k; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            unionFind.union(a, b); // 处理合根关系
        }

        System.out.println(unionFind.countPlants()); // 输出合根植物数量
        scanner.close();
    }
}

2019年第十届蓝桥杯省赛大学A组真题 修改数组

题目描述: 给定一个长度为 N 的数组A [A1,A2,···,AN],数组中有可能有重复出现的整数。

现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改A2,A3,⋅⋅⋅,AN

当修改 Ai 时,小明会检查 Ai 是否在 A1 ~ Ai - 1中出现过。如果出现过,则小明会给 Ai 加上 1 ;如果新的 Ai 仍在之前出现过,小明会持续给Ai 加 1 ,直 到 Ai 没有在 A1 ~ Ai - 1中出现过。

AN 也经过上述修改之后,显然 A 数组中就没有重复的整数了。

现在给定初始的 A 数组,请你计算出最终的 A 数组。

输入:

第一行包含一个整数 N 。

第二行包含 N 个整数 A1,A2,⋅⋅⋅,AN。

其中,1 ≤ N ≤ 100000,1 ≤ Ai ≤ 1000000

输出:

输出 N 个整数,依次是最终的 A1,A2,⋅⋅⋅,AN。

输入输出样例:

输入

5
2 1 1 3 4

输出

2 1 3 4 

解题思路:

这道题目可以巧妙地运用并查集的思想来解决。核心在于维护一个记录已出现数字的集合,并针对每个新读入的数字,动态地更新这个集合。具体思路如下:

  1. 初始化并查集:初始化一个并查集,用于维护每个已出现数字的下一个未出现数字。

  2. 逐个处理数组中的元素

    • 如果当前数字之前没出现过,则它应该保持原值不变,且加入到集合中。此后,如果再次遇到这个数字,我们就知道需要输出这个数字加1。为此,我们把这个数字在并查集中的根节点设置为这个数字加1。
    • 如果当前数字之前已经出现过,则这个数字应变成其在并查集中的根节点的值。由于根节点的值代表着当前数字的下一个未出现的数字,因此直接使用根节点的值作为新值。同时,更新根节点的值为它自己加1,以便下次使用。
  3. 输出处理后的结果:每处理一个数字后,直接输出它经过处理后的值。不需要额外的数组来存储处理后的结果。

这种方法利用并查集有效地维护了一个动态更新的集合,对于每个新读入的数字,我们可以快速判断它是否已经出现过,并找到对应的新值。这个过程中,利用并查集的“合并”和“查找”操作,保证了算法的高效性。

// 并查集类
class UnionFind {
    private int[] parent; // 父节点数组

    // 构造函数,初始化并查集
    public UnionFind(int size) {
        parent = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i; // 初始时,每个元素的父节点是它自己
        }
    }

    // 查找操作:找到元素 x 的根节点
    public int find(int x) {
        if (x != parent[x]) {
            parent[x] = find(parent[x]); // 路径压缩,将x的父节点设置为其根节点
        }
        return parent[x];
    }

    // 合并操作:将元素 x 和 y 所在的集合合并
    public void union(int x, int y) {
        int rootX = find(x); // 找到x的根节点
        int rootY = find(y); // 找到y的根节点
        if (rootX != rootY) {
            parent[rootX] = rootY; // 将x的根节点的父节点设置为y的根节点
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // 读入数组的长度
        UnionFind uf = new UnionFind(1000001); // 创建一个并查集,大小设为1000001

        for (int i = 0; i < n; i++) {
            int currentNum = scanner.nextInt(); // 读入当前数字
            int root = uf.find(currentNum); // 找到该数字在并查集中的根节点
            System.out.print(root + " "); // 输出该根节点(处理后的数字)

            if (root != 1000000) { // 如果根节点不是最大值
                uf.union(root, root + 1); // 将这个数字与它的下一个数字合并
            }
        }

        scanner.close();
    }
}

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

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

相关文章

Java基础学习: JDK动态代理

文章目录 一、什么是JDK动态代理二、JDK动态代理的特点三、JDK动态代理类如何使用四、JDK动态代理原理分析1、创建代理对象2、生成代理类 一、什么是JDK动态代理 JDK动态代理是Java提供的一种动态生成代理类和代理对象的技术。它主要利用Java的反射机制实现&#xff0c;在运行…

Lucene及概念介绍

Lucene及概念介绍 基础概念倒排索引索引合并分析查询语句的构成 基础概念 Document&#xff1a;我们一次查询或更新的载体&#xff0c;对比于实体类 Field&#xff1a;字段&#xff0c;是key-value格式的数据&#xff0c;对比实体类的字段 Item&#xff1a;一个单词&#xff0…

【计算机网络】四层负载均衡和七层负载均衡

前言 1、分层方式 首先我们知道&#xff0c;在计算机网络中&#xff0c;常用的协议分层方式&#xff1a;OSI和TCP/IP&#xff0c;以及实际生产中使用的协议划分方式。 在OSI中&#xff0c;各层的职责如下&#xff1a; 应用层&#xff1a;对软件提供接口以使程序能使用网络服…

都江堰操作系统系统架构图

都江堰操作系统设计思想源于中国传统的“天人合一&#xff0c;道法自然”哲学思想&#xff0c;内核调度系统采用事件调度&#xff0c;全球首创&#xff0c;突破单机桎梏&#xff0c;实现异构网络调度&#xff0c;开拓新赛道&#xff0c;实现换道超车。“有事就动&#xff0c;没…

Linux的中间件

我们先补充点关于awk的内容 awk的用法其实很广。 $0 表示整条记录 变量&#xff1a; NF 一行中有多少个字段&#xff08;表示字段数&#xff09; NR &#xff1a; 代表当前记录的序号&#xff0c;从1开始计数。每读取一条记录&#xff0c;NR的值就会自动增加1。&#xff08;…

Applied Spatial Statistics(一)统计推断

Applied Spatial Statistics&#xff08;一&#xff09;统计推断 1.统计推断&#xff1a;Bootstrap 置信区间 本笔记本演示了如何使用引导方法构建统计数据的置信区间。 我们还将检查 CI 的覆盖概率。 构建 Bootstrap 置信区间检查覆盖概率Bootstrap CI 相关系数 import nu…

数据挖掘入门项目二手交易车价格预测之特征工程

文章目录 目标常见的特征工程具体步骤1. 导入数据2. 删除异常值3. 特征构造3.1 为树模型构造特征3.2 为LR NN 之类的模型构造特征 4. 特征筛选过滤式包裹式嵌入式 5. 总结 本文数据集来自阿里天池&#xff1a;https://tianchi.aliyun.com/competition/entrance/231784/informat…

Debian linux版本下运行的openmediavault网盘 千兆网卡升级万兆

一、适用场景 1、使用vmware ESXi虚拟化平台运行多种不同应用服务器时&#xff0c;其中网盘服务器采用开源的openmediavault搭建&#xff1b; 2、将老专业服务器升级千兆网为万兆网&#xff1b; 3、需要转移的数据量大的企业或用户&#xff1b; 4、从服务器到服务器的数据转移…

LeetCode刷题【链表,图论,回溯】

目录 链表138. 随机链表的复制148. 排序链表146. LRU 缓存 图论200. 岛屿数量994. 腐烂的橘子207. 课程表 回溯 链表 138. 随机链表的复制 给你一个长度为 n 的链表&#xff0c;每个节点包含一个额外增加的随机指针 random &#xff0c;该指针可以指向链表中的任何节点或空节…

基于知识图谱的个性化学习推荐系统的设计与实现(论文+源码)_kaic

摘 要 Abstract 1 绪 论 1.1 研究背景及意义 1.2 国内外现状研究 1.3 研究工作和论文结构 2 相关技术 2.1 HTML 语言 2.2 Python 语言 2.3 数据库技术 2.4 Django 框架 3 系统分析 3.1 需求概述 3.2 系统可行性分析 3.2.1 技术可行性 3.2.2 经济可行性 3.2.3 操作可行性 3.3 功…

网络基础二补充——json与http协议

五、市面上常用序列化和反序列化工具 ​ 常用的有&#xff1a;json、protobuf、xml三种方案&#xff1b; 5.1json的使用 1.安装jsoncpp库&#xff0c;是一个第三方的开发库文件&#xff1b; sudo yum install -y jsoncpp-devel2.使用json ​ 经常使用的头文件是json.h&…

Python之Opencv教程(2):图像边缘检测

1、什么是边缘检测 OpenCV中的边缘检测是一种常见的图像处理技术&#xff0c;用于检测图像中物体边缘的位置。常用的边缘检测算法包括Sobel算子、Scharr算子、Laplacian算子和Canny边缘检测算法等。下面将介绍使用OpenCV实现这些边缘检测算法的方法。 2、边缘检测的作用 边缘…

C语言---自定义类型:联合体和枚举

文章目录 前言1. 联合体类型的声明1.1 联合体类型的声明1.2 联合体的特点1.4 联合体大小的计算1.5 联合的一个练习 2.枚举2.1 枚举类型的声明2.2 枚举类型的优点 前言 上一篇我们学习了自定义类型—结构体&#xff0c;大家会发现&#xff0c;构建一个结构体时&#xff0c;有些…

程序数据模型由OS还是硬件架构决定?

文章目录 前言硬件架构的作用OS的作用编译器的角色OS的数据模型参考 前言 在文章 1>>32的结果是1还是0 中提到了数据模型 L P 64 LP64 LP64 &#xff0c;并提出这个数据模型主要是由 U n i x Unix Unix 以及类 U n i x Unix Unix 的操作系统使用居多&#xff0c;例如…

macOS Catalina for mac (macos 10.15系统)v10.15.7正式版

macOS Catalina是苹果公司专为麦金塔电脑推出的桌面操作系统&#xff0c;是macOS的第16个主要版本。它继承了苹果一贯的优雅与高效&#xff0c;不仅引入了分割视图和侧边栏&#xff0c;还带来了全新的音乐和播客应用&#xff0c;极大地提升了用户体验。在隐私保护和安全性方面&…

java学习总结以及考试总结

1.对象的this引用 this引用用于区分成员变量和局部变量&#xff0c;this引用的一定的指的是成员变量 所以说this语句的作用就是区分成员变量和局部变量&#xff08;如何呢&#xff09; package com.temo.test1;public class student{private String name;//成员变量private …

Optimizer神经网络中各种优化器介绍

1. SGD 1.1 batch-GD 每次更新使用全部的样本&#xff0c;注意会对所有的样本取均值&#xff0c;这样每次更新的速度慢。计算量大。 1.2 SGD 每次随机取一个样本。这样更新速度更快。SGD算法在于每次只去拟合一个训练样本&#xff0c;这使得在梯度下降过程中不需去用所有训…

OpenEuler华为欧拉系统安装教程及联网配置

OpenEuler简介 openEuler是一款开源操作系统。当前openEuler内核源于Linux&#xff0c;支持鲲鹏及其它多种处理器&#xff0c;能够充分释放计算芯片的潜能&#xff0c;是由全球开源贡献者构建的高效、稳定、安全的开源操作系统&#xff0c;适用于数据库、大数据、云计算、人工智…

【Laravel】07 快速套用一个网站模板

【Laravel】07 快速套用一个网站模板 1. 新增post表2.补充 &#xff1a;生成Model、Controller、迁移文件3. 使用php artisan tinker4. 网站模板下载 课程地址 1. 新增post表 在Model中创建Post (base) ➜ example-app php artisan make:model Post Model created successfu…

力扣 1035. 不相交的线

题目来源&#xff1a;https://leetcode.cn/problems/uncrossed-lines/description/ C题解&#xff1a;经过细细一推导&#xff0c;就发现跟力扣 1143. 最长公共子序列-CSDN博客 换汤不换药。 直线不能相交&#xff0c;说明元素顺序不能改变&#xff0c;求可以绘制的最大连线数…