图论基础：如何高效寻找无向图中度数最大的节点

好的，我们先来分析一下这个问题。 ### 🎯 问题理解 - 我们有 `n` 个节点，编号 `0` 到 `n-1`。 - 有 `m` 条边，表示节点之间的连接。 - 每个节点的**度数**就是与它相连的边的数量。 - 我们要找到**度数最大**的节点，如果度数相同，取**编号最小**的那个。 - 输出这个节点的编号和它的度数。 ### 📊 思路 1. 用一个数组 `degree[n]` 来记录每个节点的度数，初始化为 0。 2. 读入每条边 `(u, v)`： - 因为是无向边，所以 `degree[u]++`，`degree[v]++`。 3. 遍历 `degree` 数组，找到度数最大且编号最小的节点。 4. 输出结果。 ### ⚙️ 复杂度分析 - 时间复杂度：O(n + m)，完全可行（n ≤ 1000, m ≤ O(n²)）。 - 空间复杂度：O(n)。 ### 💻 C++ 实现 ```cpp #include <iostream> #include <vector> using namespace std; int main() { int n, m; cin >> n >> m; vector<int> degree(n, 0); // 初始化度数为0 for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; degree[u]++; degree[v]++; } int maxNode = 0; int maxDegree = degree[0]; for (int i = 1; i < n; i++) { if (degree[i] > maxDegree) { maxDegree = degree[i]; maxNode = i; } // 如果度数相等，我们保留编号小的，所以这里不需要处理相等情况 // 因为我们是顺序遍历，且只在度数严格大于时才更新 } cout << maxNode << " " << maxDegree << endl; return 0; } ``` ### 🔍 关键点解释 - `vector<int> degree(n, 0)`：创建大小为 `n` 的向量，所有元素初始化为 0。 - 读边时，`degree[u]++` 和 `degree[v]++`：因为是无向图，每条边对两个端点的度数贡献都是 1。 - 查找最大值时，从 `i = 1` 开始与当前最大值比较： - 如果 `degree[i] > maxDegree`，更新最大值和节点编号。 - 如果相等，不更新，这样就保证了编号最小的节点被保留。 ### 🧪 测试样例 输入： ``` 5 6 0 1 0 2 1 2 1 3 2 3 3 4 ``` - 计算度数： - 节点0: 边 (0,1), (0,2) → 度 = 2 - 节点1: 边 (0,1), (1,2), (1,3) → 度 = 3 - 节点2: 边 (0,2), (1,2), (2,3) → 度 = 3 - 节点3: 边 (1,3), (2,3), (3,4) → 度 = 3 - 节点4: 边 (3,4) → 度 = 1 - 最大度数是 3，节点 1、2、3 都是 3，取编号最小的 **1**。 输出： ``` 1 3 ``` 与题目样例一致。 ### 🚀 进阶与注意事项 1. **图表示**：本题不需要建完整的邻接表，只需要统计度数，因此用 `degree` 数组是最简单高效的。 2. **自环与重边**：题目没有明确说明，但一般传统题中，输入保证 `u != v` 且没有重边。如果有重边，上述代码依然正确，因为每条边都会增加度数。 3. **边界情况**： - `m = 0`：所有节点度数为 0，最大值是 0，节点是 0。 - `n = 1`：度数为 0，输出 `0 0`。 4. **性能**：对于 n=1000，m 最大约 50 万，O(m) 的读入和操作在 1000ms 内完全足够。 5. **可读性**：变量命名清晰，逻辑直接，符合竞赛代码风格。 ### 📝 开发建议 - 在竞赛中，这类“统计+找最值”的题目很常见，务必确保理解清楚“并列时取编号最小”的处理方式。 - 可以封装成函数以提高代码模块化，但本题简单，直接写在 `main` 中更快捷。 - 注意输入输出使用 `cin/cout` 在本题数据量下足够快，如果数据量增大，可考虑使用 `scanf/printf` 或关闭同步流。 ######[AI写代码神器 | 1124点数解答 | 2026-04-10 21:49:55]