P3436 [POI2006] PRO-Professor Szu
题意描述不太清楚，就算到达 \(n\) 可绕一圈再回来，且数据里图不连通。考虑先求出强连通分量，缩完点后建反图在 \(\text{DAG}\) 上跑 \(\text{dp}\) 计数，注意只记那些从 \(n\) 点开始可达的，如果路径上有一个强连通分量里有边，意味着可以在这个强连通分量里反复走环，它及它的后继都是 \(\text{inf}\)。（输出方案时的点是原图中的，而非缩完点后的）
[ARC092F] Two Faced Edges
求强连通分量，缩点。考虑缩点后 \(\text{DAG}\) 上一条边 \(v \to u\)，翻转后强连通分量个数只能减少，且当且仅当 \(v\) 到 \(u\) 还有一条不经过这个边的路径，以每一个点为起点做一遍拓扑 \(O(n \times (n + m))\) 求出。而对于一个强连通分量里的边 \(v \to u\)，翻转后改变数量当且仅当 \(v \to u\) 是 \(v\) 到 \(u\) 的必经边。考虑怎么求，以每个点为起点顺序枚举它的出边（编号为 \(1\) 到 \(k\)），\(\text{dfs}\) 到每个点记录第一次到该点时来源的起点出边编号，再倒序枚举一次起点出边做一遍 \(\text{dfs}\)，若两次起点 \(v\) 到 \(u\) 的出边编号相同，则该边为必经边，复杂度同样为\(O(n \times (n + m))\)。