华为OD机试高频题解析：并查集巧解朋友圈个数问题

1. 项目概述从一道真题看华为OD机试的核心考察点最近在帮几个准备华为OD机试的朋友做模拟面试和真题复盘发现“朋友圈个数”这道题出现的频率相当高尤其是在B卷和C卷的双机位考试中。很多朋友一看到“朋友圈”、“社交网络”这些字眼下意识就往复杂的图论算法上想结果要么是思路卡壳要么是代码写得冗长且容易出错。实际上这道题的核心远没有名字听起来那么“社交”它本质上是一个经典的并查集Union-Find应用问题是检验候选人基础数据结构掌握程度和问题抽象能力的绝佳试金石。这道题通常的题干描述是给定一个n x n的矩阵M来表示一个班级中n位学生的朋友关系。如果M[i][j] 1则表示第i个学生和第j个学生互为朋友关系注意朋友关系具有传递性且自己和自己一定是朋友即M[i][i] 1。要求计算这个班级里一共有多少个“朋友圈”。所谓朋友圈就是指所有直接或间接通过朋友关系连接起来的学生构成的一个集合。这其实就是求无向图中连通分量的个数。为什么华为OD机试尤其是采用双机位监考的B/C卷会青睐这类题目我结合多年的面试官经验和与招聘团队的交流总结出几点第一它考察基本功不涉及偏门算法但能清晰区分出候选人对并查集、深度优先搜索DFS、广度优先搜索BFS等基础工具的掌握是否扎实。第二它考察问题抽象能力能否迅速将“朋友圈”这个生活场景抽象为图论中的连通分量问题。第三它考察代码实现与边界处理并查集的路径压缩、按秩合并等优化以及输入矩阵的边界检查都是编码严谨性的体现。第四在双机位环境下考察抗压与思维清晰度摄像头监控下能否冷静分析、写出简洁高效的代码本身就是一种素质筛选。接下来我将以C实现为例彻底拆解这道题。我会先带大家理解问题本质和并查集的核心思想然后给出从最朴素实现到高度优化的完整代码并附上详细的逐行注释。最后我会分享在双机位考试环境下的实战策略、常见“坑点”以及如何应对变种题目。无论你是正在备战华为OD还是想巩固图论基础这篇近万字的深度解析都能让你有所收获。2. 核心思路拆解为什么并查集是此题的最优解面对“求朋友圈个数”这个问题初学者可能会想到几种方法。我们不妨先快速分析一下这有助于理解为什么并查集是近乎完美的选择。2.1 问题本质与算法选型分析题目给出的n x n矩阵M在计算机科学中有一个更专业的名字图的邻接矩阵。在这个矩阵里每个学生是图中的一个节点值为1的位置代表两个节点之间存在一条无向边。我们要找的“朋友圈个数”就是在这个无向图中互不相连的子图即连通分量的数量。基于这个定义我们至少有三种思路深度/广度优先搜索DFS/BFS从任意一个未被访问的节点出发进行一次DFS或BFS遍历所有能到达的节点这些节点构成一个朋友圈。然后寻找下一个未被访问的节点重复此过程。访问过的节点总数等于n时停止。朋友圈个数就是发起搜索的次数。并查集Union-Find初始化时每个学生自成一个小集合一个朋友圈。然后遍历矩阵的上三角因为矩阵是对称的每当发现M[i][j] 1且i ! j就将学生i和学生j所在的集合进行“合并”Union。遍历完成后统计有多少个不同的“根”节点这个数量就是朋友圈的个数。传递闭包Floyd-Warshall变种利用动态规划思想通过三重循环来逐步推导出所有节点之间的连通性。这种方法在本题中显得大材小用时间复杂度高O(n³)空间复杂度也高一般不采用。为什么并查集更优时间复杂度DFS/BFS的时间复杂度是 O(n²)因为最坏需要检查整个矩阵n个节点每个节点可能关联n-1条边。并查集在使用了路径压缩和按秩合并优化后每次Find和Union操作的平均时间复杂度可以近似看作O(α(n))其中 α(n) 是阿克曼函数的反函数增长极其缓慢对于任何实际可能输入的 n其值都不会超过5。因此整体复杂度依然是O(n²)但常数因子更小。空间复杂度DFS/BFS需要额外的visited数组O(n)和可能使用的队列/栈空间。并查集只需要一个大小为n的父节点数组parent和一个可选的秩数组rank也是 O(n)。思维与编码简洁性这是关键。并查集将“动态合并集合”和“查询所属集合”这两个操作抽象成了两个非常清晰的函数find和unionSet。整个解题框架变得异常简洁初始化 - 遍历矩阵合并朋友 - 统计根节点数量。代码结构清晰不易出错。相比之下DFS/BFS需要显式地构建邻接表或直接使用矩阵进行递归/迭代代码逻辑相对分散。符合问题语义“朋友圈”本身就是一个动态合并的过程并查集“集合合并”的概念与之完全契合思考起来非常直观。因此在华为OD机试这种要求快速、准确实现的环境下并查集是实现“朋友圈个数”题目的首选和标准答案。2.2 并查集Union-Find原理解析与生活化类比并查集是一种树型的数据结构用于处理一些不相交集合的合并及查询问题。它主要支持两种操作Find(x)查询元素x属于哪个集合。通常通过不断查找父节点直到找到根节点根节点的父节点是它自己来确定。Union(x, y)将元素x和元素y所在的集合合并成一个集合。我们可以用一个生活中的例子来理解想象一个大型公司里有多个项目组。最开始每个人都是一个独立的项目组自成一派。公司管理系统需要记录两件事1) 查询某个人在哪个项目组Find。2) 把两个项目组合并成一个Union。初始状态我们用数组parent来表示。parent[i] i表示第i个人的“上级”就是他自己他是自己项目组的“根”组长。Find操作想知道张三下标3在哪个组就去看他的上级parent[3]。如果parent[3] ! 3说明他不是组长那就再去找他上级的上级直到找到某个人k满足parent[k] k这个人就是该组的根/组长。这个过程就是“找祖宗”。Union操作现在要把张三下标3的组和李四下标5的组合并。系统会先找到张三的根rootX Find(3)再找到李四的根rootY Find(5)。如果rootX ! rootY说明是两个不同的组那么就把其中一个组的根比如rootY的上级设置为另一个组的根rootX即parent[rootY] rootX。这样两个组就合并了以后查询组内任何人最终都会找到rootX这个共同的根。关键优化路径压缩Path Compression在Find操作的过程中当我们找到根节点后把沿途经过的所有节点的父节点都直接设置为根节点。这样下次再查询这些节点时就能以近乎 O(1) 的速度找到根。就像公司里张三找到了大老板后直接把他的直属上级改成了大老板以后他汇报工作一步到位。按秩合并Union by Rank在Union操作时我们不是随意地将一个根挂到另一个根下面。我们维护一个rank数组记录每个根节点所在树的“高度”的近似值秩。合并时总是将秩较小的树合并到秩较大的树下。这样可以避免树退化成一条链保证查找效率。就像合并两个部门把人数少的部门并入人数多的部门管理结构变动更小。将这两个优化结合起来并查集的效率就变得非常高。下面我们就将这套理论转化为C代码。3. C实现详解从基础版到优化版理解了原理我们开始动手实现。我会先给出一个最直观、未优化的版本然后逐步加入优化最后给出在机试中推荐使用的“标准答案”版本。每一行代码我都会配上详细注释。3.1 并查集类的设计与实现首先我们设计一个UnionFind类将并查集的数据和操作封装起来。这是良好的编程习惯也便于在解题函数中清晰调用。#include vector using namespace std; class UnionFind { private: vectorint parent; // 父节点数组parent[i]表示i的父节点 vectorint rank; // 秩数组rank[i]表示以i为根的树的秩高度上界 int count; // 连通分量的个数即朋友圈个数 public: // 构造函数初始化n个元素的并查集 UnionFind(int n) { count n; // 初始时每个人自成一个朋友圈 parent.resize(n); rank.resize(n, 1); // 初始秩为1 for (int i 0; i n; i) { parent[i] i; // 每个节点的父节点指向自己 } } // 查找操作带路径压缩 int find(int x) { // 如果x不是根节点父节点不是自己 if (parent[x] ! x) { // 递归查找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) return; // 按秩合并将秩小的树合并到秩大的树下 if (rank[rootX] rank[rootY]) { parent[rootX] rootY; // rootX挂到rootY下 } else if (rank[rootX] rank[rootY]) { parent[rootY] rootX; // rootY挂到rootX下 } else { // 秩相等时任意合并但被合并的树的秩需要加1 parent[rootY] rootX; rank[rootX]; // 因为两棵树高度相同合并后高度1 } count--; // 每成功合并一次朋友圈总数减1 } // 获取当前连通分量朋友圈的数量 int getCount() const { return count; } };代码关键点解读初始化在构造函数中我们将count初始化为n因为最初有n个独立个体。parent数组的每个元素初始化为自身下标rank数组初始化为1。find函数中的路径压缩parent[x] find(parent[x])这行代码是递归实现的路径压缩。它不仅在本次查找中返回了根节点还顺便把从x到根节点路径上的所有节点的父节点都直接更新为了根节点。这是一个非常巧妙的“懒更新”优化。unionSet函数中的按秩合并我们总是先找到两个元素的根。比较根的rank值将rank小的根挂到rank大的根下。如果rank相等则选择一种合并方式这里将rootY挂到rootX下并将rootX的rank加1。这个操作保证了合并后的树不会无意义地增高维持了平衡。count的维护在每次成功合并后我们将count减1。这样在合并操作全部完成后count自然就是剩余朋友圈的数量无需再遍历统计。这是一个提升效率的小技巧。3.2 主解题函数实现有了强大的UnionFind类主函数就变得异常简洁。我们的任务就是遍历关系矩阵调用并查集进行合并。int findCircleNum(vectorvectorint M) { int n M.size(); // 学生总数 if (n 0) return 0; // 边界情况处理 UnionFind uf(n); // 初始化并查集包含n个独立集合 // 遍历关系矩阵。由于矩阵是对称的且对角线是自己我们只需遍历上三角部分(i j) for (int i 0; i n; i) { for (int j i 1; j n; j) { // j从i1开始避免重复和遍历对角线 if (M[i][j] 1) { // 如果i和j是朋友 uf.unionSet(i, j); // 合并他们所在的朋友圈 } } } // 合并完成后并查集内部的count就是朋友圈的个数 return uf.getCount(); }代码关键点解读边界检查首先检查输入矩阵是否为空这是良好的防御性编程习惯。遍历优化注意到朋友关系矩阵M是对称的M[i][j] M[j][i]并且对角线M[i][i]一定是1自己是自己的朋友。因此我们只需要遍历矩阵的上三角部分i j这可以将遍历次数从 n² 减少到大约 n²/2虽然时间复杂度量级没变但常数减半在实际运行中是有意义的优化也体现了对问题的细致思考。逻辑清晰算法的核心逻辑就是“见友即合”。只要M[i][j]为1就调用uf.unionSet(i, j)。并查集会自动处理重复合并和集合计数。3.3 复杂度分析与对比让我们从理论层面分析一下这个方案的效率时间复杂度初始化并查集需要 O(n)。双重循环遍历矩阵的上三角部分循环次数为 n*(n-1)/2即 O(n²)。在循环内部每次unionSet操作会调用两次find。使用了路径压缩和按秩优化的并查集find和unionSet的均摊时间复杂度是 O(α(n))近似为常数。因此总的时间复杂度为O(n² * α(n)) ≈ O(n²)。空间复杂度主要是并查集内部的两个数组parent和rank各占用 O(n) 空间因此总空间复杂度为O(n)。作为对比如果使用DFS/BFS解法DFS实现需要递归栈或显式栈最坏空间复杂度 O(n)当图退化成链时递归深度为n。时间复杂度同样为 O(n²)因为需要检查每个可能的边即矩阵中的每个1。BFS实现需要队列空间复杂度在最坏情况下也是 O(n)。时间复杂度同样为 O(n²)。从代码实现角度看并查集的解法将复杂的图遍历过程封装在了unionSet中主函数逻辑极其简洁在紧张的机试环境中更不容易出错。4. 双机位环境下的实战策略与避坑指南华为OD机试采用双机位监考意味着你的屏幕、周围环境以及你的操作都在监控之下。在这种高压环境下解题不仅仅是写出正确的代码更是对心理素质、编码习惯和应试策略的综合考验。结合“朋友圈个数”这道题我分享一些关键的实战策略。4.1 编码前的思考与规划前5分钟不要一看到题目就埋头敲代码。双机位考试通常时间充足2-3小时合理的规划能避免后期返工。仔细审题明确输入输出再次确认输入是vectorvectorint还是int[][]输出是int。确认“朋友关系”是否具有传递性、对称性题目已明确。这是最基本的但紧张时容易看错。在注释区或草稿纸上画出思路即使题目简单也建议用注释快速写下你的算法步骤。例如// 1. 边界判断矩阵为空 // 2. 初始化并查集 UFcount n // 3. 遍历矩阵上三角M[i][j]1 则 UF.union(i, j) // 4. 返回 UF.getCount()这能让你的思路更清晰也方便在检查时快速回顾。预估复杂度选择最稳方案对于此题并查集是最优解。但在考场上如果你对并查集实现不自信DFS/BFS也是完全正确的解也能拿到满分。选择你最有把握、能一次写对的方法。在高压下代码的“正确性”远高于“最优性”的细微差别。4.2 编码实现中的细节与“坑点”即使思路正确代码细节也决定成败。以下是本题容易出错的地方坑点1并查集find函数的递归与栈溢出我上面给出的find函数使用了递归实现路径压缩简洁明了。但在极端情况下比如n非常大且初始时树很深递归可能导致栈溢出。在机试环境中这通常不是问题因为递归深度被路径压缩控制得很好。但为了绝对稳健你可以使用迭代写法int find(int x) { int root x; // 先找到根节点 root while (parent[root] ! root) { root parent[root]; } // 路径压缩将从x到root路径上的所有节点直接挂到root下 while (parent[x] ! root) { int next parent[x]; parent[x] root; x next; } return root; }迭代写法稍长但避免了递归风险。在时间有限的情况下写你最熟悉的版本。坑点2unionSet中忘记检查rootX rootY这是一个逻辑错误。如果两个元素已经在同一个集合再进行合并操作虽然不会导致错误但会无谓地增加rank如果按秩合并逻辑不严谨的话并且可能使count错误地减少。所以if (rootX rootY) return;这行检查必不可少。坑点3遍历矩阵时的重复合并这是性能和心理上的“坑”。如果你遍历了整个矩阵包括下三角和对角线会导致对角线M[i][i]为1如果对此进行unionSet(i, i)会在并查集中调用find(i)和find(i)然后判断rootX rootY而返回。这是无意义的操作浪费了时间。M[i][j]和M[j][i]都表示同一条边合并两次是完全冗余的。 因此务必使用for (int j i 1; ...)来遍历上三角。这虽然是小优化但能体现你的代码素养。坑点4输入矩阵的维度与有效性题目通常保证输入是有效的n x n矩阵。但养成防御性编程的习惯是好的。可以在函数开头加入if (n 0) return 0; for (const auto row : M) { if (row.size() ! n) { // 理论上题目不会出现但可以处理或抛出异常 return -1; // 或根据要求处理 } }4.3 调试与测试用例设计在机试环境中通常有自测用例功能。写完代码后务必设计几个测试用例进行验证。必须测试的几种情况边界情况n 0(空矩阵)n 1(只有一个学生)。你的代码应该返回 0 和 1。全连通情况所有学生都互为朋友即矩阵全为1除对角线。结果应为1。全不连通情况只有对角线为1其他全为0。结果应为n。普通情况例如 n3, M [[1,1,0],[1,1,0],[0,0,1]]。前两个学生是朋友第三个独立。结果应为2。链式关系例如 n4, 只有 M[0][1]M[1][2]M[2][3]1及对称位置其他为0。这4个人通过传递性在一个朋友圈结果应为1。这是测试并查集合并传递性的好例子。在本地IDE或机试系统的自测框中用这些用例跑一遍。如果时间允许可以单步调试一下unionSet的过程观察parent和count的变化加深理解。4.4 双机位考试的通用建议环境与设备确保网络稳定摄像头和麦克风正常工作。提前关闭所有不相关的软件、网页尤其是通讯软件避免被误判为作弊。专注题目本身双机位意在防作弊你只需专注于自己的屏幕和编码。不要有多余的动作如长时间看旁边、自言自语正常思考即可。时间管理像“朋友圈个数”这类中等难度题目建议在20-25分钟内完成包括思考、编码、测试。如果卡壳超过10分钟果断考虑换一种思路比如从并查集换到DFS或先做下一题。代码风格保持代码整洁适当添加注释尤其是算法关键步骤。良好的命名如UnionFind,findCircleNum也能提升印象分。遇到问题如果系统或题目描述有问题及时使用考试界面提供的求助功能与监考员沟通。5. 变种与拓展如何应对题目微调真正的机试真题可能会在基础版本上做一些微调以增加难度或考察应变能力。掌握核心原理后这些变种都能迎刃而解。5.1 变种1朋友圈大小求最大朋友圈的人数题目变化不仅要求朋友圈个数还要求返回最大的那个朋友圈有多少人。解题思路并查集依然是最佳工具。我们需要在合并集合的同时维护每个集合的大小。修改UnionFind类增加一个vectorint size数组初始化时每个集合的size为1。修改unionSet方法合并两个集合时将小集合的size加到小集合的size上。例如将rootY合并到rootX则size[rootX] size[rootY]。新增方法添加一个getMaxSize()方法遍历所有根节点找到最大的size[root]。核心代码修改示例class UnionFind { private: vectorint parent; vectorint sz; // 记录每个根节点所在集合的大小 int count; int maxSize; // 记录最大集合的大小 public: UnionFind(int n) : count(n), maxSize(1) { parent.resize(n); sz.resize(n, 1); // 初始大小都为1 for (int i 0; i n; i) parent[i] i; } void unionSet(int x, int y) { int rootX find(x); int rootY find(y); if (rootX rootY) return; // 按大小合并将小集合合并到大集合 if (sz[rootX] sz[rootY]) { parent[rootX] rootY; sz[rootY] sz[rootX]; maxSize max(maxSize, sz[rootY]); } else { parent[rootY] rootX; sz[rootX] sz[rootY]; maxSize max(maxSize, sz[rootX]); } count--; } int getMaxSize() const { return maxSize; } // ... find, getCount 方法不变 };主函数在调用后除了uf.getCount()还可以调用uf.getMaxSize()获得最大朋友圈人数。5.2 变种2关系矩阵非对称或为有向图题目变化朋友关系可能是单向的有向图即M[i][j]1不代表M[j][i]1。或者M[i][j]可能表示i认识j但j不一定认识i。解题思路这彻底改变了问题的性质“朋友圈”连通分量的概念在有向图中对应的是“强连通分量”。求强连通分量需要使用Kosaraju算法或Tarjan算法复杂度依然是 O(n²)但代码复杂得多。如果题目明确说明“认识关系不具有对称性但朋友圈定义为相互认识的一组人”那么这就是求有向图的强连通分量。如果题目说明“只要i认识j他们就属于同一个朋友圈”即关系具有传递性但不对称那么这等价于在由M定义的有向图上求其传递闭包的连通分量。这可以通过Floyd-Warshall算法变种O(n³)或对每个节点进行DFS/BFSO(n²)来解决。在华为OD机试中这类复杂变种出现概率较低。但如果遇到首先要冷静审题明确题目对“朋友圈”的新定义。一旦确认是有向图问题应果断选择你掌握的有向图算法模板。5.3 变种3关系以边列表形式给出题目变化输入不再是n x n矩阵而是给出学生总数n和一个关系列表edges其中edges[i] [a, b]表示学生a和学生b是朋友。解题思路这反而简化了问题我们不需要遍历矩阵只需要遍历edges列表即可。并查集的代码几乎不用变主函数修改如下int findCircleNum(int n, vectorvectorint edges) { UnionFind uf(n); for (const auto edge : edges) { uf.unionSet(edge[0], edge[1]); } return uf.getCount(); }这种形式在LeetCode等平台更常见。它省去了 O(n²) 的矩阵遍历复杂度取决于边的数量E为 O(E * α(n))。5.4 举一反三并查集的其他应用场景熟练掌握并查集能解决一大类“动态连通性”问题。在华为OD或其他算法面试中你可能会遇到它的“亲戚”岛屿数量LeetCode 200二维网格中的连通区域计数通常用DFS/BFS但也可以用并查集。账户合并LeetCode 721根据邮箱关联合并账户本质是并查集哈希表。冗余连接LeetCode 684/685在一棵树中添加一条边后形成环找出可以删去的边使得图恢复为树。并查集可以高效地检测环。等式方程的可满足性LeetCode 990处理和!关系用并查集维护相等关系集合。其核心模式都是将元素视为点将给定的“关系”视为连接点的边通过并查集动态维护这些点所属的集合。当你发现题目中出现了“分组”、“归类”、“连通”、“合并”这些关键词时就该想到并查集这个利器了。6. 从这道题看华为OD机试的备考方向“朋友圈个数”这道题就像一面镜子清晰地映照出华为OD机试尤其是软件算法方向的考察重点。通过对这道题的深度剖析我们可以总结出更普适的备考策略。6.1 算法与数据结构核心考点梳理华为OD机试的题库A/B/C/D/E卷虽然题目众多但核心考点相对集中。除了并查集以下数据结构和算法必须牢固掌握数组与字符串操作双指针、滑动窗口、前缀和、哈希表计数。这是几乎所有题目的基础。链表反转、合并、环检测、快慢指针。栈与队列单调栈、优先队列堆的应用。树与图二叉树的遍历前中后序、层序、DFS/BFS、回溯法、二叉搜索树性质、最近公共祖先。图论除了连通分量还有最短路径Dijkstra、拓扑排序等。动态规划线性DP、背包问题、字符串匹配DP编辑距离等。这是区分度较高的部分。排序与搜索快速排序、归并排序、二分查找及其变种。贪心算法区间调度、分配问题等。备考时应以LeetCode Hot 100和剑指Offer中的经典题目为主要练习材料按照专题进行突破。对于每一类算法不仅要会做更要理解其适用场景、时间空间复杂度以及代码模板。6.2 编码能力与工程习惯机试不是算法竞赛它同时考察工程实现能力。这体现在代码健壮性处理边界条件空输入、极端值、防御性编程。代码可读性良好的变量/函数命名、适当的注释、清晰的代码结构。像我们上面将并查集封装成类就是很好的实践。模块化思维将复杂功能拆解为独立的函数或类降低耦合度。例如把并查集的操作封装起来主函数逻辑就非常干净。测试意识养成写完代码后用几个典型用例边界、常规、特殊快速验证的习惯。在平时的练习中就要模拟考试环境在限定时间内完成题目并检查自己的代码是否符合上述要求。6.3 心理素质与应试技巧双机位环境会放大紧张情绪。除了技术准备心理建设同样重要模拟实战找一些在线OJ平台设定时间进行全真模拟。适应在压力下思考。时间分配通常机试有2-3道题难度可能递增。建议简单题如本题在30分钟内解决中等题留出45-60分钟难题至少留出40分钟思考。如果一道题卡住超过15分钟毫无头绪先跳过做后面的。调试策略如果自测不通过先不要慌。用最简单的测试用例比如n2单步调试或者用cout/printf打印关键变量如并查集的parent数组的中间状态往往能快速定位逻辑错误。善用草稿纸在思考复杂算法时在纸上画图比如树的遍历路径、状态转移表能极大帮助理清思路。双机位考试通常允许使用空白草稿纸。“朋友圈个数”这道题就像一位老朋友它不刁难你但认真对待它它能帮你巩固基础、建立信心、摸清考试脉络。希望这篇超过5000字的解析能帮你不仅解好这一道题更能掌握应对一整类问题的方法论。在备考的路上扎实的基础和清晰的思路永远是你最可靠的伙伴。