NeFut Logo NeFut
中 Admin Login

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

Published at: 2026-05-27 09:17 Last updated: 2026-06-06 13:04
#C++ #Tutorial

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

2. Dimensionality Reduction of Functional Graph Forests

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

  1. A core cycle (composed of residual nodes).
  2. 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.

  1. Initialization: Enqueue all points where deg[i] == 1 (leaf nodes) into the standard queue.
  2. 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 Practical Pitfall Guide

  1. Confusing the initial enqueuing threshold of "inward functional graphs" and "undirected functional graphs": In directed inward functional graphs (where each node has exactly one outgoing edge), the topological sorting should enqueue according to the directed graph's in-degree in_degree == 0. In undirected functional graphs, due to the lack of direction in edges, the initial enqueuing threshold must be strictly written as deg[i] == 1 (leaf nodes). If the degree of the undirected graph is mistakenly written as == 0, it will lead to the topological queue being empty initially, causing the entire pruning system to collapse, and the core cycle will not be exposed.
  2. Overlooking scanning of functional graph forests (disconnected): Many competition problems provide graphs that are not a complete functional graph but are composed of multiple mutually disconnected functional graphs, forming a functional graph forest. Participants, after completing topological pruning, may miss the state of other isolated functional graphs' cycles if they habitually start from node 1 to pull the cycle. Iron Rule: It is essential to perform a global scan using for (int i = 1; i <= n; ++i) in the main function; if in_ring[i] remains true, it indicates a new cycle has been triggered, necessitating a separate call to the cycle processing function.

Classic NOIP/Luogu Problems

1. Luogu P2607 [ZJOI2008] Knights

  1. Construct an undirected graph, count the degree of each point, and use Kahn's topological sorting to violently prune all non-cycle branches from the outside in. During the pruning process, simultaneously perform dynamic programming: rolling up the combat contribution from the branches to their “direct superior” root node on the core cycle.
  2. After the topological sorting is empty, the unvisited points are strictly locked as the core cycle. Traverse the entire graph to find each cycle, and use the “two-dimensional DP forced severance” method to calculate the maximum values under the two self-consistent branches of “forcing not to select the first node on the cycle” and “forcing to select the first node (thus the last node must not be selected)”, accumulating to get the final answer.

2. Luogu P1453 City Beautification / City Affairs

Original Source: local://12.5
[h] Back to Home
© 2026 Nefut. | About Us | Contact Us | Privacy Policy | RSS