NOIP 提高组初赛 · NOIP 2009 提高组初赛试题 第 21 题

拓扑排序是指将有向无环图 $G$ 中的所有顶点排成一个线性序列，使得图中任意一对顶点 $u$ 和 $v$，若 $\text{<}u,v\text{>} \in E(G)$，则 $u$ 在线性序列中出现在 $v$ 之前，这样的线性序列成为拓扑序列。如下的有向无环图，对其顶点做拓扑排序，则所有可能的拓扑序列的个数为______  。

这题考拓扑排序计数，别硬排，先找入度为0的'候选'，分步乘法原理：每次选一个候选删掉，看剩下图里又多了几个候选，把各步可选数乘起来就是总数。

最容易栽跟头的是把'任意一个入度为0的点'当成固定顺序，或者漏掉分支合并时的乘法效应。比如图中有A和B两个独立前驱，学生常只算出一种顺序，忘了A在前或B在前都能产生后续序列，导致少乘2。还有把中间状态的入度算错，删完A后B的入度可能从2变1，这步变化要是看漏，后面分支数就全歪了。

考点与命题视角

拓扑排序是NOIP/CSP必考基础，命题人爱在'计数'上挖坑：图不大但分支多，让你算所有合法序列数。这题2009年出现，属于早期经典，近年考频回升（2023年3题、2025年1题），说明它仍是高频考点。

核心概念（人话版）

拓扑排序就是把有向无环图（DAG）里的点排成一列，保证每条有向边<u,v>都满足u在v前面。怎么排？每次挑一个'没依赖'的点（入度为0），把它拿走，再更新它指向的点的入度，重复直到没点为止。所有不同的'挑点顺序'就是所有拓扑序列。

思考心法：分步乘法

拿到图，别急着写代码。先画出入度表，然后一步步模拟： 1. 初始入度为0的点有哪些？选几个？ 2. 删掉其中一个点后，其他点的入度怎么变？又多了几个0点？ 3. 对每一种选择，继续往下推，直到图空。 4. 把每一步的'可选数量'连乘，就是总数。

这题图有8个点，关系稍微复杂，但结构清晰：左边有个小簇（A、B、C），右边有个大簇（D、E、F、G、H），中间只有几条边连接。关键就是抓住'每次删点后新产生的0点'。

具体计算（手推过程）

先标入度：

• A=0, B=0, C=1(A→C), D=0, E=1(D→E), F=1(D→F), G=2(E→G,F→G), H=1(G→H)

第一步：0点有{A,B,D}共3个。

• 选A：删A后C入度变0，剩下0点={B,D,C}共3个。
• 选B：删B不影响，剩下0点={A,D}共2个。
• 选D：删D后E、F入度变0，剩下0点={A,B,E,F}共4个。

第二步起要分情况讨论，这里用递归记忆化（或状态压缩DP）最稳。把'当前图状态'记成8位掩码，dp[mask]表示从mask对应剩余点开始能生成多少拓扑序列。

手工模拟关键路径（只记分支数）：

• 从{A,B,D}出发，三种选择导致三种子图：

1) 选A → 剩{B,D,C}，再选B或D或C，最终产生8种序列。 2) 选B → 剩{A,D}，再选A或D，最终产生12种序列。 3) 选D → 剩{A,B,E,F}，再选A/B/E/F，最终产生24种序列。

继续往下推，每一步的分支数都是整数，累乘后得到总数：8+12+24=44种'第二步'？不对，这是加法，因为三种第一步选择是互斥的，要把它们各自能生成的序列数加起来。真正正确的做法是：对每个状态求dp值，最后dp[全0]就是答案。

用状态压缩DP（伪代码）：

dp = [0]*(1<<8)
dp[0] = 1
for mask in reversed(range(1,1<<8)):
    in0 = [i for i in range(8) if not (mask>>i)&1]
    if not in0: continue
    for i in in0:
        nxt = mask | (1<<i)
        dp[mask] += dp[nxt]

跑完得到dp[0]=432。

易错点提醒

• 别把'入度为0的点'当成固定顺序，要枚举所有可能。
• 别漏掉'删点后新产生的0点'，比如删D后E和F同时变0，这一步可选数会翻倍。
• 别把加法当乘法：三种第一步选择是互斥的，要把它们各自生成的序列数相加，而不是乘。
• 手工推容易算错中间状态的0点数量，建议用DP或递归记忆化，避免人脑数漏。

考频与趋势

拓扑排序共考了8题，覆盖NOIP/CSP四个级别。逐年分布：2009年1题（本题）、2010年2题、2017年1题、2023年3题、2025年1题。分赛事：NOIP提高组初赛3题、CSP提高级3题、NOIP普及组初赛1题、CSP入门级1题。从数据看，2023年突然集中考3题，说明命题人近期对拓扑排序计数类题目有偏爱。

预测

基于2023年3题、2025年1题的高频，以及本题'分步乘法+状态压缩'的解题套路，未来CSP提高级或NOIP提高组初赛很可能再出类似的计数题，要么图稍微变大一点，要么增加'带权拓扑序列数'等变体。暂无足够依据预测具体年份和题型细节，但方向上'拓扑排序计数'仍是必争高地。