专栏文章

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

个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minojo7c
此快照首次捕获于
2025/12/02 05:47
3 个月前
此快照最后确认于
2025/12/02 05:47
3 个月前
查看原文

T3

我们发现,在阅读一号书前,有一些限定的书是必须阅读的。由于这些阅读有先后顺序,其实我们很容易就能想到拓扑
但是这道题跟普通拓扑的差别就在于,我们只需要输出必须要读的书的编号,无关的书籍编号是不能计算在内的
既然这些书必须要和11号书联系,那么我们只需要跑一遍以编号11的结点为起始的dfsdfs来标记和11直接/间接联系的结点即可。
在建边时,我们为了方便搜索以及拓扑,我们可以建反图。跑完拓扑排序时保存结点,反序输出

T4

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

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

评论

0 条评论,欢迎与作者交流。

正在加载评论...