专栏文章
都是你的错,一个半小时!(拓扑)
个人记录参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @minojo7c
- 此快照首次捕获于
- 2025/12/02 05:47 3 个月前
- 此快照最后确认于
- 2025/12/02 05:47 3 个月前
T3
我们发现,在阅读一号书前,有一些限定的书是必须阅读的。由于这些阅读有先后顺序,其实我们很容易就能想到拓扑
但是这道题跟普通拓扑的差别就在于,我们只需要输出必须要读的书的编号,无关的书籍编号是不能计算在内的
既然这些书必须要和号书联系,那么我们只需要跑一遍以编号的结点为起始的来标记和直接/间接联系的结点即可。
在建边时,我们为了方便搜索以及拓扑,我们可以建反图。跑完拓扑排序时保存结点,反序输出
T4
这道题需要求满足从该点出发能无限跑的顶点。
解法一:
因为可以无限跑的一定是环,根据样例解释也可以知道:如果一个点能够到达一个环,那么这个点也会计算在内。只需要统计环内的点以及可以到这些点的其他点即可
解法二:
由于拓扑排序时,如果这一张有向图有环,那么在跑拓扑时环上的点和与环链接的点是不会被遍历的。我们只需要统计被遍历的点数量,那么答案就是
相关推荐
评论
共 0 条评论,欢迎与作者交流。
正在加载评论...