2024蓝桥杯省赛B组“传送阵”题解

15303105423 · 发表于昨天 16:22

一、题目解读

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. 竞赛启示：图论题中需灵活处理环与连通分量，结合题目特性设计高效策略。
来源：蓝桥杯题解