Topological Sorting and Dynamic Programming for Basal Tre...

Core Logic and Mathematical Principles

Topological sorting is often seamlessly integrated with the topological decomposition of functional graphs (pseudo-trees) in advanced applications of graph theory.

A functional graph is defined as a weakly connected graph consisting of $N$ nodes and $N$ edges. Because the number of edges is exactly equal to the number of nodes, it possesses extremely unique properties in mathematical topology: the entire graph contains exactly one directed (or undirected) cycle, and each node on the cycle serves as a root node, giving rise to independent tree branches (subtrees).

In inward functional graphs (where each node has exactly one outgoing edge) or undirected functional graphs, using topological sorting to separate cycles from trees (the peeling tactic) is a standard prerequisite for solving the majority of functional graph problems.

1. Dynamics of Topological Pruning Convergence

Physical Meaning: In functional graphs, the leaf nodes of the tree branches must have an in-degree (or degree in undirected graphs) of $1$. In contrast, the core cycle at the center must have a degree of at least $2$ for all its nodes, as it forms a closed loop without external interference.
Peeling Process: We perform a standard Kahn's topological sort on the entire graph (taking undirected graphs as an example, we enqueue nodes with degrees $\text{deg(node)} \text{ } \leq 1$). Each time we pop a branch node, we logically sever its edges to adjacent nodes. Since topological sorting progresses from the outside in, layer by layer towards the core, all purely branch nodes will be seamlessly popped and marked.
Algebraic Determination (Core Cycle Exposure): When the topological queue is completely empty and the algorithm terminates, the spatial state of the graph undergoes an asymmetric collapse. At this point, all nodes that have not been accessed by topological sorting (visited[i] == false or residual degree $>1$) mathematically constitute the core cycle of the functional graph.

2. Dimensionality Reduction of Functional Graph Forests

After the cleansing of topological sorting, the complex functional graph is elegantly decomposed into two parts:

A core cycle (composed of residual nodes).
Several independent subtrees (composed of nodes extracted by topological sorting), where the root of each tree corresponds to a node on the cycle.

This spatial decomposition allows us to employ a combination tactic of “tree DP + rolling relaxation on the cycle”: first, independently run tree DP on each subtree extracted by topological sorting, aggregating the energy (state values) from the branches to the root node on the cycle; then flatten the core cycle into a one-dimensional array and run dynamic programming or a two-pointer technique on the cycle to achieve the global optimal solution.

Algorithm Derivation and State Design

Taking the maximum independent set of the undirected functional graph (a ballroom without superiors) as an example for state design.

1. State Design for Topological Pruning

Define a one-dimensional counting array deg[i] to record the degree of each node.

Initialization: Enqueue all points where deg[i] == 1 (leaf nodes) into the standard queue.

State Relaxation and Convergence:

while (!q.empty()) {
 int u = q.front(); q.pop();
 in_ring[u] = false; // Mark this point as removed from the core cycle, belonging to the branch part
 for (int v : adj[u]) {
     if (deg[v] > 1) {
         // During the convergence from branches to cycles, simultaneously perform state transitions on the subtree (tree 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++ Standard Source Code (Template for Topological Sorting to Extract Core Cycle of Functional Graph)

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

const int MAXN = 100005;

std::vector<int> adj[MAXN];
int deg[MAXN];
bool in_ring[MAXN]; // Record whether the node ultimately remains in the core cycle

// dp[i][0] indicates the maximum global value obtainable by the subtree rooted at i when i is not selected
// dp[i][1] indicates the maximum global value obtainable by the subtree rooted at i when i is selected
long long dp[MAXN][2]; 
long long weight[MAXN];

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

    // 1. Initialize physical boundaries: enqueue all leaf branch nodes with degree 1
    for (int i = 1; i <= n; ++i) {
        in_ring[i] = true; // Assume everyone is in the cycle
        dp[i][0] = 0;
        dp[i][1] = weight[i]; // If the root node is selected, it initially obtains its own value
        if (deg[i] == 1) {
            q.push(i);
        }
    }

    // 2. Topological pruning: peel branches from the outside in, while simultaneously performing tree DP from the bottom up
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        in_ring[u] = false; // Consumed by the topological sequence, indicating it is not a node on the cycle

        for (size_t i = 0; i < adj[u].size(); ++i) {
            int v = adj[u][i];
            if (deg[v] > 1) {
                // Classic state machine transition for tree DP:
                // If node v is not selected, its branch child node u can be selected or not
                dp[v][0] += std::max(dp[u][0], dp[u][1]);
                // If node v is selected, then its branch child node u must not be selected
                dp[v][1] += dp[u][0];

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

// Perform convergence calculations to sever the cycle on the core cycle
long long solve_ring(int start_node) {
    // Extract cycle nodes sequentially into a one-dimensional array along the edges with deg > 1
    std::vector<int> ring_nodes;
    int curr = start_node;

    while (true) {
        ring_nodes.push_back(curr);
        in_ring[curr] = false; // Forcefully mark as visited to prevent infinite loops
        int next_node = -1;
        for (size_t i = 0; i < adj[curr].size(); ++i) {
            int v = adj[curr][i];
            if (in_ring[v]) { // Find the next adjacent point still in the cycle
                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]);

    // Perform one-dimensional DP on cycle nodes twice (forced severance concept)
    // Branch A: Forcibly do not select the first node in the cycle ring_nodes[0]
    std::vector<long long> f0(m, 0), f1(m, 0);
    f0[0] = dp[ring_nodes[0]][0];
    f1[0] = -1e15; // Assign a very small value, representing absolute non-selection
    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]);

    // Branch B: Forcibly select the first node in the cycle ring_nodes[0] -> the last node must not be selected
    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]; // Forcefully restrict the last node from being selected, can only take 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. Run topological sorting, peeling off all branch segments, and fully aggregating subtree energy to the core cycle nodes
    topo_dress_basal_tree(n);

    // 2. Traverse the entire graph; if a node is still in the cycle, it indicates a new independent functional graph's core cycle has been found
    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。拓扑排序在此处展现了极为高超的图拓扑结构净化与降维能力。

Topological Sorting and Dynamic Programming for Basal Trees: Efficient Maximum Independent Set Solution