蓝桥杯2024省赛B组传送阵问题：环检测算法精解

一、问题背景

题目模拟了一个传送阵系统，每个传送点指向另一个传送点，形成若干传送环。要求找出通过添加最少的传送通道（最多一条）能够形成的最大传送环的大小。

二、核心算法思路

1. 环检测算法：识别图中的所有环

2. 环统计策略：记录最大和次大环

3. 优化可能性分析：考虑合并相邻环的情况

三、完整代码解析（带注释）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);  // 关闭同步提升IO速度
    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;  // cnt记录环大小，j为当前节点
        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. 环统计优化：维护最大和次大环的大小，为后续优化提供基础

3. 相邻环检测：检查是否存在物理相邻但属于不同环的传送点

4. 结果计算策略：考虑两种优化可能（简单连接和合并相邻环）

五、复杂度分析

• 时间复杂度：O(n) 每个节点只被处理一次

• 空间复杂度：O(n) 用于存储环标记和环大小

六、实际应用场景

这种环检测算法广泛应用于：

1. 网络路由检测

2. 内存管理中的循环引用检测

3. 游戏中的传送系统设计

4. 社交网络中的关系环分析

参考：蓝桥杯省赛B组传送阵