华为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: vector<int> parent; // 父节点数组，parent[i]表示i的父节点 vector<int> 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(vector<vector<int>>& 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从i+1开始，避免重复和遍历对角线 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小时），合理的规划能避免后期返工。

仔细审题，明确输入输出：再次确认输入是vector<vector<int>>还是int[][]，输出是int。确认“朋友关系”是否具有传递性、对称性（题目已明确）。这是最基本的，但紧张时容易看错。
在注释区或草稿纸上画出思路：即使题目简单，也建议用注释快速写下你的算法步骤。例如：
```
// 1. 边界判断：矩阵为空 // 2. 初始化并查集 UF，count = 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; }

迭代写法稍长，但避免了递归风险。在时间有限的情况下，写你最熟悉的版本。

坑点2：unionSet中忘记检查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。
普通情况：例如 n=3, M = [[1,1,0],[1,1,0],[0,0,1]]。前两个学生是朋友，第三个独立。结果应为2。
链式关系：例如 n=4, 只有 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类：增加一个vector<int> size数组，初始化时每个集合的size为1。
修改unionSet方法：合并两个集合时，将小集合的size加到小集合的size上。例如，将rootY合并到rootX，则size[rootX] += size[rootY]。
新增方法：添加一个getMaxSize()方法，遍历所有根节点，找到最大的size[root]。

核心代码修改示例：

class UnionFind { private: vector<int> parent; vector<int> 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/BFS（O(n²)）来解决。

在华为OD机试中，这类复杂变种出现概率较低。但如果遇到，首先要冷静审题，明确题目对“朋友圈”的新定义。一旦确认是有向图问题，应果断选择你掌握的有向图算法模板。

5.3 变种3：关系以边列表形式给出

题目变化：输入不再是n x n矩阵，而是给出学生总数n，和一个关系列表edges，其中edges[i] = [a, b]表示学生a和学生b是朋友。

解题思路：这反而简化了问题！我们不需要遍历矩阵，只需要遍历edges列表即可。并查集的代码几乎不用变，主函数修改如下：

int findCircleNum(int n, vector<vector<int>>& 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分钟毫无头绪，先跳过做后面的。
调试策略：如果自测不通过，先不要慌。用最简单的测试用例（比如n=2）单步调试，或者用cout/printf打印关键变量（如并查集的parent数组）的中间状态，往往能快速定位逻辑错误。
善用草稿纸：在思考复杂算法时，在纸上画图（比如树的遍历路径、状态转移表）能极大帮助理清思路。双机位考试通常允许使用空白草稿纸。

“朋友圈个数”这道题，就像一位老朋友，它不刁难你，但认真对待它，它能帮你巩固基础、建立信心、摸清考试脉络。希望这篇超过5000字的解析，能帮你不仅解好这一道题，更能掌握应对一整类问题的方法论。在备考的路上，扎实的基础和清晰的思路，永远是你最可靠的伙伴。