📊 C++ 高效求解社交网络用户关注量与粉丝量（图论出度入度基础）

好的，我们先来分析一下这道题，然后我会给出详细的C++解决方案和开发建议。 ## 🎯 题目分析 这道题本质上是在一个**有向图**中，计算指定节点 `x` 的**出度**和**入度**。 - **出度**：从节点 `x` 出发的边的数量，即 `x` 关注的人数。 - **入度**：指向节点 `x` 的边的数量，即 `x` 的粉丝数。 由于 `n ≤ 1000`，`m ≤ 10000`，数据规模不大，我们可以用简单的邻接表或直接计数的方法来解决。 ## 🛠️ 准备工作 **环境要求**： - 任何支持 C++11 及以上的编译器（如 g++、clang++、MSVC）。 - 无需额外依赖库。 **编译命令示例**： ```bash g++ -std=c++11 -O2 solution.cpp -o solution ``` ## 💡 解决方案 最直接高效的方法是：在读取每条边 `(u, v)` 时，直接判断它是否与目标用户 `x` 相关，并累加计数。 ### 核心算法步骤 1. 读取 `n`, `m`。 2. 初始化两个计数器 `out_degree = 0` 和 `in_degree = 0`。 3. 循环 `m` 次，读取每条边 `(u, v)`： - 如果 `u == x`，则 `out_degree++`（`x` 关注了别人）。 - 如果 `v == x`，则 `in_degree++`（别人关注了 `x`）。 4. 读取目标用户 `x`。 5. 输出 `out_degree` 和 `in_degree`。 ### 📝 C++ 代码实现 ```cpp #include <iostream> using namespace std; int main() { int n, m; cin >> n >> m; int out_degree = 0, in_degree = 0; // 读取所有关注关系并直接统计 for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; // 注意：此时我们还不知道 x 是多少，所以不能在这里判断。 // 我们需要先存储这些边，或者重新思考处理逻辑。 } int x; cin >> x; // 重新读取输入？不，我们需要将边存储起来。 // 更正：更好的方法是先读入所有边到数组，或者使用更优的方案： // 方案1：存储所有边，然后遍历两次（一次统计出度，一次统计入度）。空间 O(m)，时间 O(m)。 // 方案2：因为 m ≤ 10000，n ≤ 1000，我们可以用邻接矩阵或邻接表，但直接存储边数组更简单。 } ``` 上面的代码有个逻辑错误：我们在读取边的时候还不知道 `x` 是谁。因此需要调整。 **修正后的高效方案**：先读取所有边并存储，然后读取 `x`，最后遍历边数组进行统计。 ```cpp #include <iostream> #include <vector> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; // 使用两个 vector 分别存储每条边的起点和终点 vector<int> u(m), v(m); for (int i = 0; i < m; i++) { cin >> u[i] >> v[i]; } int x; cin >> x; int out_degree = 0, in_degree = 0; for (int i = 0; i < m; i++) { if (u[i] == x) out_degree++; if (v[i] == x) in_degree++; } cout << out_degree << " " << in_degree << endl; return 0; } ``` ### 🔍 代码解释 - `ios::sync_with_stdio(false); cin.tie(nullptr);`：这两行用于**关闭C++流与C标准流的同步**，并**解除 `cin` 与 `cout` 的绑定**，可以显著加快大量数据输入输出的速度（对于本题非必需，但养成好习惯）。 - `vector<int> u(m), v(m);`：创建两个大小为 `m` 的向量，分别存储每条边的起点和终点。 - 遍历所有边，检查每条边是否与 `x` 相关，并累加计数。 - 最后输出结果。 ## ⚡ 性能与优化 - **时间复杂度**：O(m)，需要遍历所有边一次进行统计。 - **空间复杂度**：O(m)，用于存储边的信息。 - 对于本题的数据范围（m ≤ 10000），该解法完全足够。 ## 🚀 进阶与扩展 1. **如果数据量极大（例如 n, m 在 10^6 级别）**： - 可以不用存储所有边，而是使用两个一维数组（或向量）`out_count[n]` 和 `in_count[n]`，在读取每条边时直接累加：`out_count[u]++; in_count[v]++;`。这样只需 O(n) 空间，且只需遍历边一次。 - 修改后的代码如下： ```cpp #include <iostream> #include <vector> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<int> out_count(n, 0), in_count(n, 0); for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; out_count[u]++; in_count[v]++; } int x; cin >> x; cout << out_count[x] << " " << in_count[x] << endl; return 0; } ``` 这个版本是**最优解**，更节省空间，且逻辑更清晰。 2. **错误处理**： - 题目保证了输入的合法性，所以无需额外检查 `u, v` 的范围。 - 在实际应用中，可以添加断言或检查以确保数组不越界。 3. **常见陷阱**： - 用户编号从 `0` 开始，直接作为数组下标即可。 - 注意 `m` 可能为 `0`，循环和数组都能正确处理。 - 注意输出格式：两个整数之间一个空格，末尾换行。 ## 📚 开发建议 1. **优先选择空间效率高的算法**：像本题的“计数数组”方法，既快又省空间，是竞赛和工程中的常见技巧。 2. **养成输入输出优化习惯**：在C++中处理大量IO时，使用 `ios::sync_with_stdio(false);` 和 `cin.tie(nullptr);` 可以提升性能。 3. **变量命名清晰**：使用 `out_count`、`in_count` 比简单的 `a`、`b` 更能体现意图。 4. **考虑扩展性**：思考如果题目变为“查询多个用户的度”，你的算法是否容易扩展？使用计数数组的方法可以轻松应对多次查询（O(1) 每次查询）。 ## 🧪 测试用例 除了题目给的样例，还可以测试边界情况： ```text 输入： 1 0 0 输出： 0 0 ``` ```text 输入： 3 3 0 1 1 2 2 0 1 输出： 1 1 ``` ## 🔗 相关资源 - [C++ Vector 文档](https://en.cppreference.com/w/cpp/container/vector) - [图的基础概念：度、出度、入度](https://en.wikipedia.org/wiki/Directed_graph#Indegree_and_outdegree) - 在线判题平台（如 Codeforces, LeetCode）上有大量类似图论基础题目，可以用于练习。 希望这个详细的解答对你有帮助！这道题是图论中最基础的入门题，核心在于理解有向图中度的概念并高效统计。 ######[AI写代码神器 | 1799点数解答 | 2026-04-10 21:44:39]