关于拓扑排序的应用
262 字
1 分钟
关于拓扑排序的应用
这道题的让我们对图中的无向边进行定向,那么我们先把无向边断开,相当于拆成若干个有向连通块,然后我们对所有点进行拓扑排序求出它们的拓扑序,然后我们就可以按照拓扑序的大小关系对无向边进行定向,证明明天再补。
很好我来补证明了。
因为有多个连通块,所以先考虑一个连通块,我们发现对于一个连通块内的点来说,点的拓扑序大小关系一定是严格与单独在这个连通块内拓扑排序的拓扑序相同,那么如果按照之前说的那样对无向边进行定向的话,因为序号小的一定只能指向序号大的,假设给你一堆有序号的点,规定只能从序号小的点向序号大的点连边,那么我们发现这样无论怎么连它都是一张DAG,此题同理。
文章分享
如果这篇文章对你有帮助,欢迎分享给更多人!
相关文章智能推荐
1
关于dp状态转移方程的设计4
算法竞赛2026-07-18
2
关于动态规划的转移1
算法竞赛2023-11-01
3
关于需要处理复杂依赖关系的题
算法竞赛2023-10-24
4
关于dp状态转移方程的设计3
算法竞赛2023-10-24
5
关于dp状态转移方程的设计2
算法竞赛2023-10-18
随机文章随机推荐

