华为OD机试C卷高频题：并查集解决“小朋友来自多少小区”问题详解-北京尧图网络

1. 项目概述与核心需求解析最近在准备华为OD机试的C卷发现“小朋友来自多少小区”这道题出现的频率相当高而且据说在真题库里的通过率表现不错。很多朋友在初次接触时可能会被题目描述绕进去觉得要处理复杂的社交关系或者图论问题。其实不然这道题的核心是一个集合合并与计数的问题本质上是并查集Union-Find的经典应用场景。我花了一些时间用C完整实现并调试通过这里把解题思路、代码实现细节以及机试中容易踩的坑系统地梳理一遍。无论你是正在备战华为OD还是想巩固一下数据结构与算法这篇内容都能给你提供一条清晰的路径。简单来说题目会给你一组数据表示哪些小朋友彼此认识通常来自同一个小区。你的任务就是根据这些“认识关系”计算出这群小朋友总共来自多少个不同的“小区”。这里的“小区”就是一个等价类彼此认识的小朋友属于同一个小区不认识的就属于不同小区。这听起来是不是很像“朋友圈”问题没错解题的钥匙就是并查集。接下来我会从问题本质、并查集原理、C实现细节到机试实战技巧一步步拆解。2. 解题思路与数据结构选型2.1 问题抽象与建模首先我们需要把模糊的自然语言描述转化为精确的计算机模型。题目输入通常是n对关系每对关系(a, b)表示小朋友a和小朋友b互相认识。所有小朋友的编号通常是连续的整数例如从1到N。输出是一个整数互不相识的群体即小区的个数。这立刻让我们联想到图论中的“连通分量”概念。如果把每个小朋友看作图中的一个节点认识关系看作一条无向边那么题目就是要求这个无向图中连通分量的数量。求连通分量可以用深度优先搜索DFS或广度优先搜索BFS但这类题目通常小朋友数量节点数和关系数量边数可能很大用搜索遍历整个图的时间复杂度是O(NE)虽然可行但代码写起来稍显繁琐且在处理合并操作时不如并查集直观高效。并查集是专门为处理这类“动态连通性”问题设计的数据结构。它支持两种高效操作Find(x)查找元素x属于哪个集合即代表元。Union(x, y)合并元素x和y所在的集合。对于本题初始时每个小朋友自成一个集合来自不同小区。每读入一条关系(a, b)就执行一次Union(a, b)操作。处理完所有关系后我们只需要统计有多少个不同的“代表元”其数量就是小区的个数。选择并查集的核心理由在于其近乎常数时间的操作效率经过路径压缩和按秩合并优化后以及代码实现简洁非常契合机试对时间复杂度和编码速度的双重要求。2.2 并查集核心操作原理解析并查集通常使用一个数组parent[]来实现。parent[i]表示节点i的“父节点”。如果parent[i] i那么i就是这个集合的“根节点”或“代表元”。查找Find目标是找到节点x所在集合的根。朴素方法是沿着父节点指针一直向上找。我们可以通过路径压缩进行优化在查找过程中将路径上每个节点的父节点都直接指向根节点。这样树的高度会大大降低后续查找会更快。int find(int x, vectorint parent) { if (parent[x] ! x) { parent[x] find(parent[x], parent); // 递归查找并压缩路径 } return parent[x]; }合并Union目标是合并x和y所在的集合。首先找到它们的根rootX和rootY。如果根相同说明它们已在同一集合无需操作。如果不同则需要将一棵树的根挂到另一棵树的根上。为了保持树的平衡我们引入按秩合并优化使用一个额外的rank[]数组或size[]数组记录每棵树的高度或大小总是将较矮的树合并到较高的树上。这样可以避免树退化成链表。void unionSets(int x, int y, vectorint parent, vectorint rank) { int rootX find(x, parent); int rootY find(y, parent); if (rootX ! rootY) { // 按秩合并 if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else { // 秩相等时任意合并但被合并的树秩要加1 parent[rootY] rootX; rank[rootX]; } } }这两种优化路径压缩按秩合并同时使用时每个操作的摊还时间复杂度接近O(α(n))其中α(n)是增长极慢的反阿克曼函数对于任何实际可能出现的n值α(n)都不会超过5因此可以认为是常数时间。3. C代码实现与逐行解读理解了原理我们来看完整的C实现。机试环境通常支持C11/14我们使用标准库即可。3.1 完整代码实现#include iostream #include vector #include unordered_set using namespace std; class UnionFind { private: vectorint parent; vectorint rank; // 按秩合并的秩 public: // 构造函数初始化n个元素各自独立 UnionFind(int n) { parent.resize(n 1); // 假设小朋友编号从1开始多分配一个空间 rank.resize(n 1, 0); // 初始秩为0 for (int i 1; i n; i) { parent[i] i; // 每个节点的父节点初始化为自己 } } // 查找操作带路径压缩 int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); // 递归压缩 } return parent[x]; } // 合并操作带按秩合并 void unite(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]; } } } // 统计不同集合的数量即不同根的数量 int countDistinctSets() { unordered_setint rootSet; // 注意我们只关心有小朋友的编号从1开始遍历 // 实际上我们需要知道总共有多少个小朋友这里假设parent.size()已知 // 更稳健的做法是传入总人数n for (size_t i 1; i parent.size(); i) { rootSet.insert(find(i)); // 找到每个元素的根并插入集合 } return rootSet.size(); } }; int main() { int n, m; // n: 小朋友数量 m: 关系对数 // 题目输入格式可能略有不同常见的是先给出n和m // 例如第一行两个整数n, m。接下来m行每行两个整数a, b。 cin n m; UnionFind uf(n); for (int i 0; i m; i) { int a, b; cin a b; uf.unite(a, b); } int communityCount uf.countDistinctSets(); cout communityCount endl; return 0; }3.2 关键代码段解析与注意事项初始化大小parent.resize(n 1)。这是一个非常关键的细节。因为题目中小朋友的编号很可能从1开始。如果我们只分配n个空间索引0到n-1那么当访问parent[n]时就会发生数组越界。多分配一个空间并将下标0闲置是一种安全且清晰的做法。在机试中务必仔细阅读输入描述确认编号起始点。find函数中的路径压缩parent[x] find(parent[x])。这行代码是效率的关键。它不仅在递归返回时把当前节点x的父节点直接指向了根节点而且递归过程中路径上的所有节点都会被压缩。这是一种“完全压缩”效果最好。unite函数中的按秩合并我们比较的是rank[rootX]和rank[rootY]。rank数组记录的是树高的上界。当两棵树高度相同时合并后树高才会增加1rank[rootX]。这保证了树的高度增长非常缓慢。统计集合数量countDistinctSets函数中我们遍历所有节点从1到n对每个节点调用find(i)找到其根然后插入到一个unordered_set哈希集合中。集合自动去重最后集合的大小就是不同根的数量即小区的数量。这里必须对每个节点重新find一次因为经过一系列的unite操作后parent[i]可能并不直接指向根如果i不是根且路径未被最近压缩只有find操作能确保得到真正的根。注意在极端情况下如果小朋友编号不是从1开始的连续整数或者总人数n没有直接给出就需要用更灵活的数据结构比如用map来代替vector。但根据华为OD机试真题的常见模式输入通常是规整的使用数组vector是最高效的选择。4. 机试实战技巧与避坑指南纸上谈兵终觉浅绝知此事要躬行。在真实的机试环境中把代码写对只是第一步如何快速、稳定地拿到满分还需要一些实战技巧。4.1 输入处理与边界条件机试的输入输出是自动判题的格式错误或边界情况处理不当会导致大量丢分。明确输入格式一定要看清楚题目描述。是n m然后m行关系吗还是先给关系对数再逐行输入小朋友的编号范围是什么题目是否保证所有小朋友编号都在1到n之间常见的坑点是“多组测试数据”题目可能没说只有一组输入你的代码需要能持续读取直到文件结束EOF。一个简单的应对方法是使用while(cin n m)包裹整个处理逻辑。// 处理可能的多组数据输入 int n, m; while (cin n m) { UnionFind uf(n); // ... 处理m对关系 // ... 输出结果 }初始化与重置如果处理多组数据切记每一组数据都要重新初始化UnionFind对象及其内部的parent和rank数组。否则上一组数据的状态会污染下一组导致错误。数组大小如前所述如果编号从1开始数组大小设为n1。如果题目明确说编号从0开始则设为n即可。这是一个高频失分点。4.2 性能优化与代码简洁性机试有时间和内存限制虽然本题数据规模通常不会卡O(NE)的算法但良好的习惯很重要。避免全局变量像parent和rank这样的数组封装在UnionFind类内部是更好的做法。这避免了全局变量在复杂题目中可能引发的命名冲突和状态管理混乱。I/O优化在C中对于大量数据输入输出可以考虑使用ios::sync_with_stdio(false);和cin.tie(nullptr);来解除C标准流与C标准流的同步关闭cin和cout的绑定可以显著提升速度。这在处理10万量级以上的输入时效果明显。int main() { ios::sync_with_stdio(false); cin.tie(nullptr); // ... 后续代码 }统计数量的优化我们之前用unordered_set来统计根的数量其插入和查找的平均时间复杂度是O(1)。另一种更节省空间的方法是在每次成功执行unite操作即两个集合真正合并时将一个全局计数器count减1。初始时count n每个人一个集合每合并一次集合数减少1。最后count的值就是答案。这样省去了最后遍历和建集合的开销。class UnionFind { // ... 其他成员 int setCount; // 集合数量 public: UnionFind(int n) : setCount(n) { ... } void unite(int x, int y) { // ... 合并逻辑 if (rootX ! rootY) { // ... 执行合并 setCount--; // 集合数减1 } } int getSetCount() const { return setCount; } };4.3 调试与自测方法机试环境可能不提供强大的调试器学会有效的自测是关键。设计测试用例基础用例n5, m3, 关系: (1,2), (2,3), (4,5)。预期输出2{1,2,3}和{4,5}两个小区。边界用例1n1, m0。只有1个小朋友没有关系。预期输出1。边界用例2n5, m0。所有人都不认识。预期输出5。边界用例3n5, m10关系数很多但可能重复或形成环。关系如(1,2), (2,1), (2,3), (3,4), (4,5), (5,1)。最终所有人应在一个集合输出1。最大规模用例在本地可以生成n100000, m200000的随机数据测试程序是否超时或内存溢出。输出中间结果在本地调试时可以在unite操作后打印parent数组观察合并过程是否正确。但在提交代码前务必移除这些调试输出。使用静态分析确保代码没有使用未初始化的变量、数组索引越界、除零错误等。这些错误在在线判题系统中可能导致“运行时错误”而非“答案错误”更难定位。5. 常见问题与排查实录在实际编写和调试过程中我遇到和收集了一些典型问题这里列出来供大家参考。问题现象可能原因排查与解决方法输出结果比预期少1数组下标错误。小朋友编号从1开始但parent数组大小为n访问parent[n]越界导致未定义行为。检查parent和rank的初始化大小确保为n1如果编号从1开始。输出结果总是1find函数没有实现路径压缩或者unite函数逻辑错误导致所有元素的根被错误地统一。1. 检查find函数确认有parent[x] find(parent[x])这行。2. 在unite中确保是对rootX和rootY进行操作而不是对x和y直接操作。3. 使用简单的测试用例单步调试。处理多组数据时第二组开始出错没有为每组数据重新初始化并查集数据结构。全局变量或类的成员变量保留了上一组数据的状态。将UnionFind uf(n);的声明放在while(cin n m)循环内部确保每次都是全新的对象。在大数据量下运行超时1.find函数没有路径压缩退化为O(n)查找。2. 使用了set而非unordered_set统计数量set是O(log n)插入。3. I/O效率低下。1. 确认路径压缩和按秩合并优化都已实现。2. 统计数量时使用unordered_set或使用setCount递减法。3. 添加ios::sync_with_stdio(false); cin.tie(nullptr);。提交后提示“段错误”或“运行时错误”几乎肯定是内存访问越界。1. 重点检查所有数组访问的下标特别是parent[x]中的x是否可能超出[0, size)或[1, size)的范围。2. 检查输入数据中是否包含非法编号如0或大于n的数。如果题目不保证需要在读取时判断并处理。一个特别隐蔽的坑在countDistinctSets函数中我们遍历i从1到parent.size()-1。这里隐含了一个假设编号从1到n的小朋友都存在。如果题目输入的关系中只出现了部分编号比如只给了关系(100, 200)但n1000那么那些未在关系中出现的小朋友会被视为独立的小区吗题目描述通常会说“有n个小朋友”意味着编号1-n都存在。如果描述模糊需要向考官澄清。在实现时更安全的做法是传入确切的n然后遍历1到n。最后再分享一个我个人的编码习惯我会把并查集的模板代码预先准备好放在编辑器的代码片段里。遇到类似“连通分量”、“分组”、“朋友的朋友”这类关键词直接套用模板然后根据具体题目微调输入输出和统计方式这能节省大量的编码和调试时间。这道“小朋友来自多少小区”就是模板的直接应用理解透彻后下次遇到“相似字符串组”、“账户合并”这类LeetCode上的并查集题目你也会觉得驾轻就熟。

华为OD机试C卷高频题：并查集解决“小朋友来自多少小区”问题详解

相关推荐

量子支持向量机(QSVM)原理与DREAMVFIA项目实践

AI提示工程架构设计：提升模型输出的精准度与适应性

Cmder：提升Windows开发效率的终极终端工具

更多资讯

最近特种工报名点如何避坑？考前押题干货全在这儿

桂平在哪考电工证2026河南最新政策下怎么考更稳妥

盐源考电工证值不值得考？实操考试心里没底怕挂科

新乡建筑工人怎么报名建筑类电工证考试避坑指南

电工证考多少题 2026河南最新政策下怎么转证更省事

培训电工证江阴报考条件与考试时间

今日更新

桐乡去哪考电工证怎么考？全国通用电工证报考全流程详解

低压电工证是必须的嘛电子证书怎么申请更稳妥

特种作业证模板工怎么报名才不会被中介坑

本周精选

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？

相关推荐

量子支持向量机(QSVM)原理与DREAMVFIA项目实践

AI提示工程架构设计：提升模型输出的精准度与适应性

Cmder：提升Windows开发效率的终极终端工具

更多资讯

最近特种工报名点如何避坑？考前押题干货全在这儿

桂平在哪考电工证2026河南最新政策下怎么考更稳妥

盐源考电工证值不值得考？实操考试心里没底怕挂科

新乡建筑工人怎么报名建筑类电工证考试 避坑指南

电工证考多少题 2026河南最新政策下怎么转证更省事

培训电工证江阴报考条件与考试时间

今日更新

桐乡去哪考电工证怎么考？全国通用电工证报考全流程详解

低压电工证是必须的嘛电子证书怎么申请更稳妥

特种作业证模板工怎么报名才不会被中介坑

本周精选

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？

新乡建筑工人怎么报名建筑类电工证考试避坑指南