会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
解题思路
本题的算法标签是「拓扑排序 + 动态规划（DAG 路径计数）」。把每个 AI 处理节点看成有向图中的一个点，依赖关系 edges[i] = [u, v] 看成一条有向边 u→v；题目保证图是 DAG，要求从 s 到 t 的不同路径条数。
最直接的想法是从 s 开始 DFS，每走到 t 就把答案加一。但路径条数可能随层数指数增长（第 8 组是 30 个「二选一」串联，共 230 条路径），枚举所有路径必然超时，所以必须用 DP 复用子问题。
DP 定义：dp[u] 表示从起点 s 到节点 u 的路径条数，初始 dp[s] = 1（从 s 到 s 有一条长度为 0 的路径）。对 DAG 做拓扑排序后，按拓扑序处理每个节点 u，对它的每条出边 u→v 执行 dp[v] += dp[u]——所有到达 u 的路径都能再走一步到 v。最终 dp[t] 就是从 s 到 t 的路径总数；若 s 到 t 不可达，dp[t] 保持 0，恰好对应题目要求。
为什么必须拓扑排序：只有保证处理 u 时，所有能到达 u 的前驱都已处理完，dp[u] 才是最终值，再往下累加才不会漏。实现上用 Kahn 算法：先把所有入度为 0 的节点入队，出队时把它的路径数推给后继并减少后继入度，后继入度归零时入队。这样每个节点和每条边都只被处理一次。
