都是你的错,一个半小时!(拓扑)

· · 个人记录

T3

我们发现,在阅读一号书前,有一些限定的书是必须阅读的。由于这些阅读有先后顺序,其实我们很容易就能想到拓扑

但是这道题跟普通拓扑的差别就在于,我们只需要输出必须要读的书的编号,无关的书籍编号是不能计算在内的

既然这些书必须要和1号书联系,那么我们只需要跑一遍以编号1的结点为起始的dfs来标记和1直接/间接联系的结点即可。

在建边时,我们为了方便搜索以及拓扑,我们可以建反图。跑完拓扑排序时保存结点,反序输出

T4

这道题需要求满足从该点出发能无限跑的顶点。

解法一:

因为可以无限跑的一定是环,根据样例解释也可以知道:如果一个点能够到达一个环,那么这个点也会计算在内。只需要统计环内的点以及可以到这些点的其他点即可

解法二:

由于拓扑排序时,如果这一张有向图有环,那么在跑拓扑时环上的点和与环链接的点是不会被遍历的。我们只需要统计被遍历的点数量cnt,那么答案就是n-cnt