很显然的一个结论：一条边 \(u \to v\) 能够被删去，当且仅当至少存在一条其它的路径从 \(u\) 通向 \(v\) 。
所以我们就建出正反两张图，对每个点开两个 bitset 维护它与其他点的连通性，这个可以通过拓扑排序预处理。
然后就枚举每一条边，拿两个端点的两个 bitset 与一下即可判断出这条边是否可以删去。
参考代码：
#include <cstdio>#include <bitset>#define rg register#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)using namespace std;template < class T > inline void read(T& s) { s = 0; int f = 0; char c = getchar(); while ('0' > c || c > '9') f |= c == '-', c = getchar(); while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar(); s = f ? -s : s;} const int _ = 3e4 + 5, __ = 1e5 + 5; int tot, phead[_], rhead[_]; struct Edge { int v, nxt; } edge[__ << 1];inline void Add_edge(int* head, int u, int v) { edge[++tot] = (Edge) { v, head[u] }, head[u] = tot; } int n, m, x[__], y[__], pdgr[_], rdgr[_];bitset < _ > pbs[_], rbs[_]; inline void toposort(int* head, int* dgr, bitset < _ > * bs) { static int hd, tl, Q[_]; hd = tl = 0; for (rg int i = 1; i <= n; ++i) if (!dgr[i]) Q[++tl] = i; while (hd < tl) { int u = Q[++hd]; for (rg int i = head[u]; i; i = edge[i].nxt) { int v = edge[i].v; bs[v] |= bs[u], bs[v][u] = 1; if (!--dgr[v]) Q[++tl] = v; } }} int main() {#ifndef ONLINE_JUDGE file("cpp");#endif read(n), read(m); for (rg int i = 1; i <= m; ++i) { read(x[i]), read(y[i]); Add_edge(phead, x[i], y[i]), ++pdgr[y[i]]; Add_edge(rhead, y[i], x[i]), ++rdgr[x[i]]; } toposort(phead, pdgr, rbs), toposort(rhead, rdgr, pbs); int ans = 0; for (rg int i = 1; i <= m; ++i) ans += (pbs[x[i]] & rbs[y[i]]).any(); printf("%d\n", ans); return 0;}
