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

11小时前比赛题解45

一、问题背景

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

二、核心算法思路

环检测算法：识别图中的所有环
环统计策略：记录最大和次大环
优化可能性分析：考虑合并相邻环的情况

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

#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;
}