都是你的错,一个半小时!(拓扑)
T3
我们发现,在阅读一号书前,有一些限定的书是必须阅读的。由于这些阅读有先后顺序,其实我们很容易就能想到拓扑
但是这道题跟普通拓扑的差别就在于,我们只需要输出必须要读的书的编号,无关的书籍编号是不能计算在内的
既然这些书必须要和
在建边时,我们为了方便搜索以及拓扑,我们可以建反图。跑完拓扑排序时保存结点,反序输出
T4
这道题需要求满足从该点出发能无限跑的顶点。
解法一:
因为可以无限跑的一定是环,根据样例解释也可以知道:如果一个点能够到达一个环,那么这个点也会计算在内。只需要统计环内的点以及可以到这些点的其他点即可
解法二:
由于拓扑排序时,如果这一张有向图有环,那么在跑拓扑时环上的点和与环链接的点是不会被遍历的。我们只需要统计被遍历的点数量