探险队选人问题题解（C++实现）

这道题的核心是将“选人约束”转化为功能图的最大独立集问题。通过分析功能图（每个节点出度≤1）的特殊结构（孤立节点+内向基环树），分组件计算最大独立集后汇总，即可得到答案。

一、问题转化与图结构分析

1. 问题本质

• 节点：每个候选人对应一个节点（编号1~n）。
• 边：若候选人i排斥a[i]（a[i]≠-1），则添加有向边i→a[i]（表示i和a[i]不能同时选）。
• 目标：找到图中“任意两节点无边相连”的最大子集（最大独立集）。

2. 关键结构：功能图

由于每个节点出度≤1，图为功能图，其连通分量仅两种：

• 孤立节点：a[i]=-1的节点（无出边，可直接选，贡献1到答案）。
• 内向基环树：由“一个环”和“指向环的内向链”组成（链上节点最终指向环，需特殊处理）。

二、核心算法思路

功能图的最大独立集 = 孤立节点贡献 + 所有内向基环树的最大独立集之和。
内向基环树的处理分两步：

1. 链的最大独立集：用线性DP计算（无循环依赖，直接递推）。
2. 环的最大独立集：拆环为链（断开一条边），分两种情况计算DP，取最大值（避免环的循环依赖）。

三、详细解题步骤

步骤1：环检测（内向基环树的核心）

通过“状态标记法”找到所有环：

• 状态0：节点未访问；
• 状态1：节点正在访问（递归路径中）；
• 状态2：节点已访问完毕。
  若递归中遇到状态1的节点，说明找到环（从该节点到当前路径末尾即为环）。

步骤2：链的DP计算

2.1 DP状态定义

对链上节点u（按“远离环→靠近环”顺序）：

• dp0[u]：不选u时，以u为起点的子链的最大独立集；
• dp1[u]：选u时，以u为起点的子链的最大独立集。

2.2 转移方程

设v = a[u]（u指向的节点）：

• 选u：v不能选 → dp1[u] = 1 + dp0[v]；
• 不选u：v可选或不选 → dp0[u] = max(dp0[v], dp1[v])。

2.3 边界条件

若u是环上节点（链的终点），先初始化dp0[u] = 0、dp1[u] = 0（后续环的DP会覆盖）。

步骤3：环的DP计算

环的循环依赖需通过“拆边”解决：

• 断开环的一条边（如(cy[0], cy.back())），将环转为链；
• 情况1：强制不选cy[0]，计算链的最大独立集；
• 情况2：强制不选cy.back()，计算链的最大独立集；
• 环的最大独立集 = max(情况1, 情况2)。

步骤4：结果汇总

• 孤立节点：每个贡献1；
• 内向基环树：环的最大独立集 + 所有附属链的最大独立集之和。

四、完整C++代码（带详细注释）

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

// 全局变量（避免函数传参繁琐，实际工程可封装为类）
vector<int> a;               // a[1..n]：每个节点的排斥对象（-1表示无）
vector<int> visited;         // 节点状态：0=未访问，1=访问中，2=访问完
vector<bool> in_cycle;       // 标记节点是否在环上
vector<vector<int>> cycles;  // 存储所有环（每个环是节点列表）
vector<int> path;            // 递归时记录当前路径
vector<int> dp0;             // dp0[u]：不选u的最大独立集
vector<int> dp1;             // dp1[u]：选u的最大独立集

/**
 * 递归检测环：找到功能图中的所有环
 * @param u 当前处理的节点
 */
void find_cycle(int u) {
    if (visited[u] == 2) return;  // 已处理完，直接返回
    if (visited[u] == 1) {        // 遇到访问中的节点，找到环
        auto it = find(path.begin(), path.end(), u);  // 定位环的起点
        vector<int> current_cycle(it, path.end());    // 截取环的节点
        cycles.push_back(current_cycle);
        for (int node : current_cycle) {
            in_cycle[node] = true;  // 标记节点在环上
        }
        return;
    }
    visited[u] = 1;  // 标记为访问中
    path.push_back(u);
    if (a[u] != -1) {  // 有排斥对象，递归处理下一个节点
        find_cycle(a[u]);
    }
    visited[u] = 2;  // 标记为处理完
    path.pop_back(); // 回溯，移除当前节点
}

/**
 * 递归计算链的DP：处理非环节点（链上节点）
 * @param u 当前链节点
 */
void dfs_chain(int u) {
    if (dp0[u] != -1) return;  // 已计算过，避免重复
    if (in_cycle[u]) {         // 环上节点（链的终点），先初始化
        dp0[u] = 0;
        dp1[u] = 0;
        return;
    }
    int v = a[u];       // u的下一个节点（指向v）
    dfs_chain(v);       // 先计算子节点v的DP
    // 状态转移
    dp1[u] = 1 + dp0[v];          // 选u → 不选v，加1（u本身）
    dp0[u] = max(dp0[v], dp1[v]); // 不选u → v可选或不选，取最大值
}

/**
 * 计算单个环的最大独立集：拆环为链，分两种情况
 * @param cy 环的节点列表
 * @return 环的最大独立集大小
 */
int calc_cycle_max(const vector<int>& cy) {
    int k = cy.size();
    if (k == 1) return 0;  // 自环：选了会排斥自己，故贡献0

    // 情况1：强制不选cy[0]，计算链cy[0]→cy[1]→...→cy[k-1]
    for (int node : cy) { dp0[node] = -1; dp1[node] = -1; } // 重置DP
    dfs_chain(cy[0]);
    dp0[cy[0]] = 0;         // 强制不选cy[0]
    dp1[cy[0]] = INT_MIN;   // 禁止选cy[0]（选了违反约束）
    for (int i = 1; i < k; ++i) {
        int v = cy[i-1];     // 前一个节点（链的顺序）
        dfs_chain(cy[i]);
        // 更新当前节点的DP值
        int new_dp0 = max(dp0[v], dp1[v]);
        int new_dp1 = 1 + dp0[v];
        dp0[cy[i]] = new_dp0;
        dp1[cy[i]] = new_dp1;
    }
    int res1 = max(dp0[cy.back()], dp1[cy.back()]);

    // 情况2：强制不选cy[k-1]，计算链cy[k-1]→cy[k-2]→...→cy[0]
    for (int node : cy) { dp0[node] = -1; dp1[node] = -1; } // 重置DP
    dfs_chain(cy.back());
    dp0[cy.back()] = 0;         // 强制不选cy[k-1]
    dp1[cy.back()] = INT_MIN;   // 禁止选cy[k-1]
    for (int i = k-2; i >= 0; --i) {
        int v = cy[i+1];     // 后一个节点（链的逆序）
        dfs_chain(cy[i]);
        // 更新当前节点的DP值
        int new_dp0 = max(dp0[v], dp1[v]);
        int new_dp1 = 1 + dp0[v];
        dp0[cy[i]] = new_dp0;
        dp1[cy[i]] = new_dp1;
    }
    int res2 = max(dp0[cy[0]], dp1[cy[0]]);

    return max(res1, res2); // 取两种情况的最大值
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cout << "请输入候选人数量n：";
    cin >> n;

    // 初始化数据（1-based索引，节点编号1~n）
    a.resize(n + 1);
    cout << "请输入每个候选人的排斥对象a[1]~a[n]（-1表示无）：\n";
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    visited.assign(n + 1, 0);
    in_cycle.assign(n + 1, false);
    cycles.clear();
    path.clear();
    dp0.assign(n + 1, -1);
    dp1.assign(n + 1, -1);

    // 步骤1：检测所有环
    for (int u = 1; u <= n; ++u) {
        if (visited[u] == 0) {
            find_cycle(u);
        }
    }

    // 步骤2：计算所有链的DP（非环节点）
    for (int u = 1; u <= n; ++u) {
        if (!in_cycle[u] && a[u] != -1) {
            dfs_chain(u);
        }
    }

    // 步骤3：汇总所有组件的贡献
    int ans = 0;
    // 1. 孤立节点的贡献（a[u]=-1，无排斥对象，直接选）
    for (int u = 1; u <= n; ++u) {
        if (a[u] == -1) {
            ans += 1;
        }
    }

    // 2. 每个内向基环树的贡献（环+附属链）
    for (const auto& cy : cycles) {
        int cycle_max = calc_cycle_max(cy); // 环的最大独立集
        int chain_max = 0;                  // 附属链的最大独立集
        // 统计“父节点在环上、自身不在环上”的链节点（链的起点）
        for (int u = 1; u <= n; ++u) {
            if (!in_cycle[u] && a[u] != -1 && in_cycle[a[u]]) {
                chain_max += max(dp0[u], dp1[u]);
            }
        }
        ans += cycle_max + chain_max;
    }

    cout << "最多可选择的候选人数：" << ans << endl;
    return 0;
}

五、示例验证

测试用例

• 输入：n=3，a = [2, 3, -1]（候选人1排斥2，2排斥3，3无排斥）。
• 图结构：1→2→3（3是孤立节点，1和2构成链，无环）。

计算过程

1. 孤立节点：3贡献1；
2. 链（1→2）：
   • 计算dp0[2] = max(dp0[3], dp1[3]) = max(0,0)=0（3是孤立节点，dp初始为0）；
   • dp1[2] = 1 + dp0[3] = 1+0=1；
   • dp0[1] = max(dp0[2], dp1[2]) = max(0,1)=1；
   • dp1[1] = 1 + dp0[2] = 1+0=1；
   • 链的最大独立集：max(dp0[1], dp1[1])=1；
3. 总答案：1（孤立节点）+1（链）=2。

六、注意事项

1. 输入格式：代码中为了交互友好，添加了输入提示，实际OJ提交时需删除提示，按OJ要求的格式读取（如直接读n和a数组）；
2. 自环处理：环长度为1时（如a[1]=1），该节点不能选，贡献0；
3. DP重置：处理环的两种情况时，需重置环上节点的DP值，避免前一次计算的干扰；
4. 递归深度：功能图的链长通常不大，递归不会栈溢出，若节点数极大，可改为迭代实现。