这是我写的第5个正式题解 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 【A85523】最大食物链计数 题目链接 点这里 题目大意 有一张 nnn 个节点，mmm 条边的有向图（这里构造方式等会再说） 最终求最大食物链的节点数量 简单来讲，最大食物链就是 * 一张图中由多条边，多个节点构成的链 * 最左端节点出度为0，最右端节点入度为0 解题思路 1. 算法选择 拓扑排序+dp维护最小值 拓扑排序简单了解 * 选择拓扑排序是因为： 可以把这题看成 而要想得到“到兔子这一步时，最大食物链的节点数量”就必须要知道“到草这一步时，最大食物链节点的数量”，这不正是拓扑排序可以解决的吗？ * 选择dp是因为：我们需要动态求解到第i部分时，最大食物链的节点数量 2. 核心思路 1. 输入这张图并更新入度、出度值 > Q：输入什么图？关系是怎样的？ > A：输入有向图，关系：g[u].push_back(v) --> u节点被v节点吃 2. 拓扑排序 * 拓扑排序注意点: 3. 结算答案 对于每个食物链顶端（出度为0） 的节点，全部往最终答案中添加dp[i]的值 易错点/坑点 题目中说了，要对20021108取模 因此对于每步可能超出20021108的运算，都需要取模 AC 代码