中山市选2011 杀人游戏
一个环上的点可以通过询问环上任意一点来确定整个环的状态，有入度的点可以通过询问它之前的点来确定。
所以我们先缩点。需要统计出所有入度为 \(0\) 的强连通分量的个数。
注意一个特殊情况，若存在一个强连通分量满足它大小为 \(1\)，且它连接到的点的入度都不小于 \(2\)，那么可以考虑把这个点放到最后来询问，以此来减少一次询问（只能减少一次）。
POI2006 Pro-Professor Szu
先缩点，若存在自环或者一个大小大于 \(1\) 的强连通块那么答案为无限大，其它直接按照拓扑序转移，中间若方案数大于 \(36500\) 就将方案数设为 \(36501\)。
APIO2009 抢掠计划
一样缩点然后 dp，中间若有一个强连通分量有 ATM 机，就给 dp 设初值。
SDOI2010 所驼门王的宝藏
给每行每列建一个虚点。
这题卡空间，可以先给行列离散化。
Two Faced Edges
考虑一条边 \(u\to v\)，有以下两个变化：
-
存在一条从 \(v\) 到 \(u\) 的路径。
-
存在一条从 \(u\) 到 \(v\) 且不经过边 \(u\to v\) 的路径。
满足上面条件中的一个，那么反转 \(u\to v\) 就会使强连通分量个数改变。
第一种情况直接 \(O(nm)\) 暴力即可。
第二种情况，可以从 \(u\) 按照顺序，记录下到 \(v\) 的 \(u\) 的出边。然后按照 \(u\) 出边顺序反着再来做一次，若两次 \(u\) 的出边不同，那么就满足第二个条件。
标签：10,连通,询问,入度,2024,出边,分量 From： https://www.cnblogs.com/ddxrS/p/18456554