G005缩点哈密顿路径拓扑排序，竞赛进阶指南中，401题u到v或v到u路径如何确定？
摘要：从u到v还是从v到u？ - AcWing 貌似数据较弱？ P10944 Going from u to v or from v to u? - 洛谷 两倍经验 已知一个有向图，要求任意两点 (u, v) 都满足 (u) 可以到达
从u到v还是从v到u？ - AcWing 貌似数据较弱？
P10944 Going from u to v or from v to u? - 洛谷 两倍经验
已知一个有向图，要求任意两点 \(u, v\) 都满足 \(u\) 可以到达 \(v\) 或 \(v\) 可以到达 \(u\) 。请你判断要求能不能成立。
不难看出强连通图是一定成立的，那我们就可以将图缩点成一个 DAG 然后判断源点的数量，如果源点数量大于 \(1\) 则一定不行，然后也不能出现支线，否则支线之间无法到达。
于是就变成了判断是否存在一条哈密顿路径。对于 DAG 来说其等价于拓扑排序的唯一性判断。