题意：给出一张 个点
条边的有向图，保证不存在重边和自环。
对于每条边，判断将其反向后（其他边不变），图中强连通分量的数量是否改变。
，，时限 。
对于边 ，若将其反向：
若
在同一个强连通分量内。
强连通分量个数不可能增加，但该强连通分量可能被破坏。
若图中存在一条
的路径，且不含该边，则不会破坏，反之则会。
若
不在同一个强连通分量内。
若图中存在一条
的路径，且不含该边，则会增加一个强连通分量，反之无变化。
记 表示“ 在同一个强连通分量内”， 表示图中存在 的路径，且不含边 。
综上所述，只有
两者之一成立，边
的答案才为 ，否则为 。
对于 ，容易使用 Tarjan
算法求出。问题的核心在于
的求解。
算法一
考虑对于每个 分别求出 。
从 开始 dfs ，将 的边表顺序翻转，再次 dfs。
若点 在两个 dfs 树中深度均为
，则说明 ，否则 。
证明：
若 ，则点 在两个 dfs 树中深度显然均为 。
下证点 在两个 dfs 树中深度均为
时， 。即 时 在两个 dfs 树中深度不可能同时为 。
时，存在另一条不走
的路径能从 到 ，记该路径的第一条边为 。
在两次 dfs 中，必然恰有一次先考虑 而后考虑 ，由于 dfs
的特性，一定会从 进而访问到 。后面考虑 时，就不会将其加入 dfs
树。
算法二
仍考虑对于每个 分别求出 。
对于某个 ， 当且仅当存在 ，满足存在简单路径 。
将 点删除，将所有直接与 相连的点记为 。
顺次考虑 ，从
开始搜索（不重复遍历之前搜过的点），所有搜到的点 （除了 本身）都能满足 。
（这里用 常数较小）
为了处理 的情况，还需反过来再跑一次。
这样的搜索复杂度是
的，瓶颈在于，无论目的地是否被标记过，我们都要再次检查出边。
考虑利用 bitset 进行优化，记目前还未发现 的 的集合为 ，点 的出边的集合为 。我们搜索时，只需考虑集合 内的元素。
下面的代码段可以用 的代价找出
bitset
内的所有元素。
1
| for(int i=T._Find_first(); i!=T.size(); i=T._Find_next(i))
|
每个点只会被搜索到一次，故复杂度为 。