基环树的拓扑排序与动态规划：高效求解最大独立集

核心逻辑与数学原理

拓扑排序在图论的高级应用中，常常与基环树（Functional Graph / Pseudo-tree）的拓扑分解无缝结合。

基环树是指一个包含 $N$ 个点和 $N$ 条边的弱连通图。由于边数恰好等于点数，它在数学拓扑上具有极其独特的性质：整张图有且仅有一个有向（或无向）环，而环上的每个节点都作为根节点，向外衍生出一棵棵独立的树状分支（子树）。

在内向基环树（每个点有且仅有一条出边）或无向基环树中，利用拓扑排序进行环与树的分离（剥离战术）是解决绝大多数基环树问题的标准前置动作。

1. 拓扑剪枝的动力学收敛

物理意义：在基环树中，树枝部分的叶子节点入度（或无向图中的度数）一定为 $1$。而位于核心中央的环，由于形成了一个闭环回路，环上所有节点的度数在没有外界干扰时至少为 $2$。
剥离过程：我们对整张图进行一次标准的 Kahn 拓扑排序（以无向图为例，将度数 $ ext{deg} ext{(node)} ext{ } ext{<= } 1$ 的节点压入队列）。每次弹出一个树枝节点，并逻辑切断它与邻接点的边。由于拓扑排序是自外向内、一层层向核心推进的，所有纯粹的树枝节点都会被无缝弹出并标记。
代数判定（核心环暴露）：当拓扑队列彻底变空、算法终止时，图的空间状态会发生非对称性坍塌。此时，所有未被拓扑排序访问过（visited[i] == false 或残留度数 $>1$）的节点，在数学上严格构成了该基环树的核心环。

2. 基环树森林的降维打击

经过拓扑排序的洗礼后，复杂的基环树被优雅地拆解为两部分：

一个核心环（由残留点组成）。
若干棵独立的子树（由被拓扑排序抽离的点组成），每棵树的根节点正好是环上的某个节点。

这种空间拆解使得我们可以使用“树上 DP ＋环上滚动松弛”的组合拳战术：先在拓扑排序抽离出来的每棵子树上独立运行树形 DP，将树枝上的能量（状态值）全量归拢、收敛到环上的根节点上；随后将核心环拉平为一维数组，在环上运行动态规划或双指针滚动，从而斩获全局最优解。

算法推导与状态设计

以无向基环树最大独立集（基环树上的没有上司的舞会）为例进行状态设计。

1. 拓扑剪枝状态设计

定义一维计数数组 deg[i] 记录每个节点的度数。

初始化：将所有 deg[i] == 1（叶子节点）的点压入标准队列。

状态松弛与收敛：

while (!q.empty()) {
 int u = q.front(); q.pop();
 in_ring[u] = false; // 标记该点已被踢出核心环，属于树枝部分
 for (int v : adj[u]) {
     if (deg[v] > 1) {
         // 在树枝向环收敛的过程中，顺便在子树上做状态转移 (树形 DP)
         dp[v][0] += std::max(dp[u][0], dp[u][1]);
         dp[v][1] += dp[u][0];
         if (--deg[v] == 1) q.push(v);
     }
 }
}

C++ 标准源码（拓扑排序剥离基环树核心环模板）

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

const int MAXN = 100005;

std::vector<int> adj[MAXN];
int deg[MAXN];
bool in_ring[MAXN]; // 记录节点最终是否留在核心环中

// dp[i][0] 表示不选 i 号点时，以 i 为根的子树能获得的全局最大价值
// dp[i][1] 表示选择 i 号点时，以 i 为根的子树能获得的全局最大价值
long long dp[MAXN][2]; 
long long weight[MAXN];

void topo_dress_basal_tree(int n) {
    std::queue<int> q;

    // 1. 初始化物理边界：将所有度数为 1 的叶子树枝节点并入队列
    for (int i = 1; i <= n; ++i) {
        in_ring[i] = true; // 默认所有人都在环上
        dp[i][0] = 0;
        dp[i][1] = weight[i]; // 选择根节点则初始获得自身价值
        if (deg[i] == 1) {
            q.push(i);
        }
    }

    // 2. 拓扑剪枝：自外向内剥离树枝，同步自底向上做树形 DP
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        in_ring[u] = false; // 被拓扑序列吞噬，说明不是环上节点

        for (size_t i = 0; i < adj[u].size(); ++i) {
            int v = adj[u][i];
            if (deg[v] > 1) {
                // 树形 DP 经典状态机转移：
                // 节点 v 不选，则其树枝子节点 u 可选可不选
                dp[v][0] += std::max(dp[u][0], dp[u][1]);
                // 节点 v 选择，则其树枝子节点 u 绝对不能选
                dp[v][1] += dp[u][0];

                deg[v]--;
                if (deg[v] == 1) {
                    q.push(v);
                }
            }
        }
    }
}

// 在核心环上进行切断环路的收敛计算
long long solve_ring(int start_node) {
    // 沿着残留的 deg > 1 的边将环路节点按顺序提取到一个一维一字型数组中
    std::vector<int> ring_nodes;
    int curr = start_node;

    while (true) {
        ring_nodes.push_back(curr);
        in_ring[curr] = false; // 强行打上访问标记，防止死循环
        int next_node = -1;
        for (size_t i = 0; i < adj[curr].size(); ++i) {
            int v = adj[curr][i];
            if (in_ring[v]) { // 寻找下一个依然在环上的邻接点
                next_node = v;
                break;
            }
        }
        if (next_node == -1) break;
        curr = next_node;
    }

    int m = ring_nodes.size();
    if (m == 0) return 0;
    if (m == 1) return std::max(dp[ring_nodes[0]][0], dp[ring_nodes[0]][1]);

    // 对环上节点进行两次一维 DP（强制切断思想）
    // 分支 A：强制不选环上第一个节点 ring_nodes[0]
    std::vector<long long> f0(m, 0), f1(m, 0);
    f0[0] = dp[ring_nodes[0]][0];
    f1[0] = -1e15; // 赋予极小值，代表绝对不选
    for (int i = 1; i < m; ++i) {
        int u = ring_nodes[i];
        f0[i] = dp[u][0] + std::max(f0[i-1], f1[i-1]);
        f1[i] = dp[u][1] + f0[i-1];
    }
    long long resA = std::max(f0[m-1], f1[m-1]);

    // 分支 B：强制选择环上第一个节点 ring_nodes[0] -> 则最后一个节点绝对不能选
    f0[0] = -1e15;
    f1[0] = dp[ring_nodes[0]][1];
    for (int i = 1; i < m; ++i) {
        int u = ring_nodes[i];
        f0[i] = dp[u][0] + std::max(f0[i-1], f1[i-1]);
        f1[i] = dp[u][1] + f0[i-1];
    }
    long long resB = f0[m-1]; // 强制限制最后一个节点不能选，只能取 f0

    return std::max(resA, resB);
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    if (!(std::cin >> n)) return 0;

    for (int i = 1; i <= n; ++i) {
        int v;
        std::cin >> weight[i] >> v;
        adj[i].push_back(v);
        adj[v].push_back(i);
        deg[i]++;
        deg[v]++;
    }

    // 1. 跑拓扑排序，剥离所有的树枝分支，并将子树能量全量收敛到核心环的节点上
    topo_dress_basal_tree(n);

    // 2. 遍历全图，若点依然在环上，说明找到了一个新的独立基环树的核心环
    long long total_max_value = 0;
    for (int i = 1; i <= n; ++i) {
        if (in_ring[i]) {
            total_max_value += solve_ring(i);
        }
    }

    std::cout << total_max_value << "\n";
    return 0;
}

NOIP 实战避坑指南

混淆“内向基环树”与“无向基环树”的初始入队门槛：在有向内向基环树中（每个点有且仅有一条出边），拓扑排序应当按照有向图入度 in_degree == 0 进队。而在无向基环树中，由于边没有方向，初始进队门槛必须严格写成 deg[i] == 1（叶子节点）。如果将无向图的度数误写成 == 0，会导致拓扑队列初始直接为空，整个剪枝系统完全瘫痪，核心环根本无法暴露。
基环树森林（非连通）遗漏扫描：很多竞赛题给出的图并不是一棵完整的基环树，而是由多棵互不连通的基环树拼凑而成的基环树森林。选手在拓扑剪枝完毕后，如果只习惯性地从 1 号点出发去拉取环，会漏掉其他孤立基环树的环路状态。铁律：必须在 main 函数中用 for (int i = 1; i <= n; ++i) 全局滚动扫描，只要 in_ring[i] 仍为真，就说明触发了新环，必须单独调用环路处理函数。

经典 NOIP/洛谷真题

1. 洛谷 P2607 [ZJOI2008] 骑士

题意描述：有 $N$ 个骑士，每个骑士都有各自的战斗力。每个骑士都有一个他最厌恶的仇敌。现在要从这些骑士中挑选一个军团，为了确保团结，任何一个骑士都不能和他的仇敌同时进入军团。求能选出的骑士战斗力之和的最大值。
问题本质与核心思路：基环树最大独立集的至尊真题。每个骑士有且仅有一个仇敌，代表每个点有且仅有一条出边，是一张标准的内向基环树森林。核心战术完全契合上述源码模型：

建立无向图，统计每个点的度数，利用 Kahn 拓扑排序从外向内暴力裁剪掉所有非环路的树枝。在裁剪过程中，顺便执行动态规划：将树枝上骑士去留的战斗力贡献滚动累加到他们位于核心环上的“直属上司”根节点上。
拓扑排序变空后，未被访问的点严格锁定为核心环。遍历全图找出每个环，通过“两次一维 DP 强制断环”法，分别计算“强制不选环上首节点”和“强制选择首节点（此时尾节点必不选）”两种自洽分枝下的极大值，累加即为最终答案。

2. 洛谷 P1453 城市美化 / 城市往事

题意描述：某城市有 $N$ 个居民点，居民点之间有 $N$ 条双向道路相连（无向基环树）。每个居民点都有一个美化价值。为了防止审美疲劳，两个相邻的居民点不能同时进行美化。现在要求在满足此限制的前提下，城市能获得的最大美化价值。
问题本质与核心思路：无向基环树最大独立集经典真题。该题与《骑士》在代数本质上完全一致，区别在于本题直接给出了无向图结构。解法同样是利用拓扑排序对度数为 1 的节点进行向内收敛剪枝，同步完成子树上的基础松弛，最后在残存的度数 $>1$ 的无向环上进行断边区间 DP。拓扑排序在此处展现了极为高超的图拓扑结构净化与降维能力。