一、题目解读2024年蓝桥杯省B组“传送阵”题目要求处理一个包含n个节点的图，节点间存在单向传输关系。每个节点i可传送至a指定的节点，形成可能存在的环结构。题目需求解从任意节点出发能到达的最长路径长度。本质上是图论中的最长路径问题，需考虑环的存在及节点间的连通性。 二、解题思路1. 预处理阶段使用标记法找出所有环，记录每个环的大小（即节点数）。 2. 统计**环和次大环尺寸。 3. 计算基础结果：若存在次大环，结果为**环+1；否则为**环。 4. 检查是否存在相邻节点属于不同环，若存在则合并两环得到更长的路径。 核心逻辑：利用环结构中的“循环路径”延长总路径，并通过节点间的连通性判断路径合并的可能性。 三、解题步骤1. 输入与初始化 读入节点数n及传输关系a。 初始化辅助数组：cycle_id记录节点所属环编号，cycle_size存储各环尺寸。 2. 环检测与尺寸统计 遍历节点，对未标记的节点i启动DFS：循环访问a直至回到起点，标记路径上的节点并计数，形成环编号及尺寸。 3. 计算基础结果 遍历cycle_size，更新**环max1和次大环max2。 结果result初始化为max1+1（若max2存在）或max1。 4. 路径合并判断 遍历相邻节点i和i+1，若所属环不同（cycle_id!= cycle_id[i+1]），标记has_adjacent为true。 若存在相邻异环节点，更新结果result为max(max1+max2, result)。 5. 输出最终结果。 四、代码与注释
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- int main() {
- ios::sync_with_stdio(false);
- cin.tie(nullptr); // 优化输入输出速度
- int n;
- cin >> n;
- vector<int> a(n + 1); // 存储传输关系
- for (int i = 1; i <= n; ++i) cin >> a[i];
-
- vector<int> cycle_id(n + 1, 0); // 节点所属环编号
- vector<int> cycle_size; // 各环尺寸
- int id = 0; // 环编号计数器
- // 预处理：找出所有环
- for (int i = 1; i <= n; ++i) {
- if (cycle_id[i]) continue; // 已标记节点跳过
- id++; // 新环编号
- int cnt = 0, j = i; // 当前节点及计数
- while (!cycle_id[j]) { // 未标记的环路径
- cycle_id[j] = id; // 标记节点
- cnt++;
- j = a[j]; // 沿传输关系移动
- }
- cycle_size.push_back(cnt); // 记录环尺寸
- }
-
- // 统计**环和次大环
- int max1 = 0, max2 = 0;
- for (int sz : cycle_size) {
- if (sz > max1) {
- max2 = max1;
- max1 = sz;
- } else if (sz > max2) {
- max2 = sz;
- }
- }
-
- // 基础结果：**环+1（若存在次大环）
- int result = (max2 > 0)? max1 + 1 : max1;
-
- // 检查相邻节点是否在不同环
- bool has_adjacent = false;
- for (int i = 1; i < n; ++i) {
- if (cycle_id[i]!= cycle_id[i + 1]) { // 环编号不同
- has_adjacent = true;
- break;
- }
- }
-
- // 路径合并：若存在异环相邻节点，更新结果
- if (has_adjacent) {
- result = max(result, max1 + max2);
- }
-
- cout << result << endl;
- return 0;
- }
五、总结1. 算法核心：通过环检测将图分解为独立环，利用环的特性计算最长路径。 2. 优化点： 时间复杂度O(n^2)：预处理环+单次遍历判断相邻环。 空间复杂度O(n)：仅需存储环编号和尺寸。 3. 拓展思考：若题目允许双向传输，需改用其他算法（如拓扑排序）处理。 4. 竞赛启示：图论题中需灵活处理环与连通分量，结合题目特性设计高效策略。
| 
发表于 