对一条边 \((u,v)\) 分两种情况讨论：在原图中是否属于强连通分量。
如果属于一个强联通分量：
考虑一对节点 \((x,y)\)，若 \((x,y)\) 路径上 \((u,v)\) 为必经之路，且 \(y\) 可以到达 \(x\)，那么反转后 \((x,y)\) 必定不属于一个强联通分量。判定的时候令 \(x=u,y=v\) 即可。
如果不属于一个强联通分量：
还是考虑一对节点 \((x,y)\)。若 \(y\) 能够到达 \(x\) 且 \(x\) 能够到达 \(u\)，\(v\) 能够到达 \(y\)，那么反转后 \((x,y)\) 必定属于一个强联通分量。判定的时候令 \(x=u,y=v\) 即可。
\(u\) 是否能到达 \(v\) 可以用 bitset 优化 Floyd \(O(\frac{n^3}{\omega})\) 求一个传递闭包，剩下考虑必经之路的问题即可。
必经之路相当于路径条数只有一条，直接对每个 \(u\) 做一遍 \(O(m)\) 的 BFS 即可。
最终复杂度 \(O(\frac{n^3}{\omega}+nm)\)。
标签：联通,ARC092F,到达,即可,属于,必经之路,分量 From： https://www.cnblogs.com/lmpp/p/16592471.html