【C++】有N种颜色的小球，开始同一种颜色小球装在同一个筐里面，颜色从1到N标号。有下面两个操作(Cab)，把颜色是b的 (源码)【独一无二】

本文主要是介绍【C++】有N种颜色的小球，开始同一种颜色小球装在同一个筐里面，颜色从1到N标号。有下面两个操作(Cab)，把颜色是b的 (源码)【独一无二】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

👉博__主👈：米码收割机
👉技__能👈：C++/Python语言
👉公众号👈：测试开发自动化【获取源码+商业合作】
👉荣__誉👈：阿里云博客专家博主、51CTO技术博主
👉专__注👈：专注主流机器人、人工智能等相关领域的开发、测试技术。

---

C++实现 并查集实现颜色球归类和查询操作

---

目录

• C++实现 并查集实现颜色球归类和查询操作
• 一、题目要求
• 二、设计思路
• • • 数据结构设计
    • 功能实现
    • 性能优化
• 三、代码展示

---

一、题目要求

有N种颜色的小球，开始同一种颜色小球装在同一个筐里面，颜色从1到N标号。有下面两个操作(Cab)，把颜色是b的球所在筐中的球都倒进颜色是a的球所在的筐。(Qc)，查询颜色是c的球所在的筐中，哪种颜色的球最多，哪种颜色的球最少，输出球的个数

输入格式
第一行两个正整数N、M。M表示一共有M个操作。(1<=N、M<=100000)。第二行是N个由空格隔开的正整数，第i个数表示颜色为i的球有ai个，ai在int范围内。接下来的M行，对应M个操作。
输出格式
对于每个查询输出一行，每行两个正整数，第一个为最大值，第二个为最小值。

👉👉👉 源码获取 关注【测试开发自动化】公众号，回复 “ 归类查询” 获取。👈👈👈

样例一input

6 6
1 2 3 4 5 6
C 1 2
C 3 4
C 5 6
C 1 3
C 1 5
Q 1

outout：

6 1

👉👉👉 源码获取 关注【测试开发自动化】公众号，回复 “ 归类查询” 获取。👈👈👈

二、设计思路

设计基于并查集数据结构，用以高效处理“合并”和“查询”操作。

数据结构设计

1. 并查集（Union-Find）结构：主要用于管理和追踪每种颜色球的归属，每个筐通过一个领导者（即并查集中的根节点）来标识。
   • parent 数组：用于表示每个节点的父节点，若 parent[x] == x，则 x 是根节点。
   • size 数组：记录每个根节点所代表的集合的大小，用于在合并时优化树的高度，以保持树的平衡，从而加速查询操作。
   • colorCount 向量：这是一个向量，其中的每个元素都是一个哈希表（unordered_map），用于存储该根节点集合中不同颜色球的数量。

👉👉👉 源码获取 关注【测试开发自动化】公众号，回复 “ 归类查询” 获取。👈👈👈

功能实现

1. 初始化：

   • 使用 initialCount 数组初始化 colorCount，这个数组记录了每种颜色球的初始数量。
   • 初始时，每种颜色的球自成一组，其根节点即其自身，且每个筐只包含一种颜色的球。

2. 合并操作（unionSet）：

   • 查找两个颜色所在集合的根节点。
   • 如果根节点不同，将一个集合合并到另一个集合。为了保持树的平衡，通常将较小的集合合并到较大的集合中（基于 size 数组）。
   • 更新根节点的 colorCount 哈希表，将被合并集合的颜色球数量加到目标集合的对应颜色上。

3. 查询操作（query）：

   • 查找指定颜色所在的集合的根节点。
   • 遍历根节点的 colorCount 哈希表，找到数量最多和最少的球，输出这两个值。

👉👉👉 源码获取 关注【测试开发自动化】公众号，回复 “ 归类查询” 获取。👈👈👈

性能优化

• 路径压缩：在查找操作中使用路径压缩技术，使得每个节点直接或间接指向根节点，减少后续查找的深度。
• 按秩合并：通过比较集合的大小（利用 size 数组），总是将较小的集合合并到较大的集合，这有助于保持并查集树的平衡，提高效率。

👉👉👉 源码获取 关注【测试开发自动化】公众号，回复 “ 归类查询” 获取。👈👈👈

---

三、代码展示

#include <iostream>
#include <vector>
#include <unordered_map>using namespace std;struct UnionFind {vector<int> parent;vector<int> size;// 代码略....>👉👉👉 源码获取 关注【测试开发自动化】公众号，回复 “ 归类查询” 获取。👈👈👈// 代码略....// 代码略....int find(int x) {if (parent[x] != x) {parent[x] = find(parent[x]);}return parent[x];}void unionSet(int x, int y) {int rootX = find(x);int rootY = find(y);if (rootX != rootY) {if (size[rootX] < size[rootY]) {swap(rootX, rootY);}parent[rootY] = rootX;size[rootX] += size[rootY];for (auto& p : colorCount[rootY]) {colorCount[rootX][p.first] += p.second;}}}// 代码略....// 代码略....// 代码略....};int main() {// 代码略.... >👉👉👉 源码获取 关注【测试开发自动化】公众号，回复 “ 归类查询” 获取。👈👈👈// 代码略....// 代码略....int N, M;cin >> N >> M;vector<int> initialCount(N);for (int i = 0; i < N; ++i) {cin >> initialCount[i];}// 代码略....// 代码略....// 代码略....return 0;
}

运行结果：

👉👉👉 源码获取 关注【测试开发自动化】公众号，回复 “ 归类查询” 获取。👈👈👈

这篇关于【C++】有N种颜色的小球，开始同一种颜色小球装在同一个筐里面，颜色从1到N标号。有下面两个操作(Cab)，把颜色是b的 (源码)【独一无二】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---