关于找环

_tobi_

·

2024-11-01 11:21:26

·

个人记录

有向图每次调用 DFS 时维护一个自增的时间戳，同一次 DFS 所有点都打上相同时间戳，如果访问到时间戳相同的点说明存在环/找到唯一环

无向图可以用 dfn，找到 dfn 比自己大的点说明找到环，且不需要处理环被找到两次的问题。对于所有环的边不相交的无向图（仙人掌），如果只需要点集不需要顺序，那么可以用 Tarjan 建圆方树

Tarjan 找 0 环只需要把 0 边提出来然后跑即可，这样 SCC 大小大于 1 的话说明整个 SCC 由 0 环构成

拓扑排序只能判断有没有环，但是无法判断某个点是否在环上。如 NOIP2017 逛公园一题就无法用拓扑排序判断 0 环的存在。