2024蓝桥杯省赛B组“传送阵”题解（C++代码+图论算法优化）
本帖最后由 19339201706 于 2025-6-15 14:45 编辑https://www.xinaozhilu.cn/zb_users/upload/2025/06/202506071749227321112127.jpg
一、题目解读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），标记has_adjacent为true。 若存在相邻异环节点，更新结果result为max(max1+max2, result)。5. 输出最终结果。四、代码与注释C++
#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;
vector<int> cycle_id(n + 1, 0); // 节点所属环编号
vector<int> cycle_size; // 各环尺寸
int id = 0; // 环编号计数器
// 预处理：找出所有环
for (int i = 1; i <= n; ++i) {
if (cycle_id) continue; // 已标记节点跳过
id++; // 新环编号
int cnt = 0, j = i; // 当前节点及计数
while (!cycle_id) { // 未标记的环路径
cycle_id = id; // 标记节点
cnt++;
j = a; // 沿传输关系移动
}
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!= cycle_id) { // 环编号不同
has_adjacent = true;
break;
}
}
// 路径合并：若存在异环相邻节点，更新结果
if (has_adjacent) {
result = max(result, max1 + max2);
}
cout << result << endl;
return 0;
}转自：2024蓝桥杯省赛B组“传送阵”题解（C++代码+图论算法优化）
页:
[1]