题面
题解
可以发现, 若 \(u\) 到 \(v\) 可由从 \(u\) 到 \(v\) 的另外一条路径而不走 \((u, v)\) 边到达, 则 \((u, v)\) 可删
正反用 bitset 维护一下传递闭包即可
Code
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <bitset>
#include <queue>
const int N = 30005;
const int M = 1e5 + 5;
using namespace std;
int n, m, cnte[2], head[2][N], in[2][N], ans;
struct edge { int to, nxt; } e[2][M];
bitset<N> bit[2][N];
queue<int> q;
template < typename T >
inline T read()
{
T x = 0, w = 1; char c = getchar();
while(c < '0' || c > '9') { if(c == '-') w = -1; c = getchar(); }
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * w;
}
inline void adde(int u, int v, int opt) { e[opt][++cnte[opt]] = (edge) { v, head[opt][u] }, head[opt][u] = cnte[opt]; }
void toposort(int opt)
{
for(int i = 1; i <= n; i++)
if(!in[opt][i]) q.push(i);
while(!q.empty())
{
int u = q.front(); q.pop();
for(int v, i = head[opt][u]; i; i = e[opt][i].nxt)
{
v = e[opt][i].to; bit[opt][v] |= bit[opt][u], bit[opt][v][u] = 1;
in[opt][v]--; if(!in[opt][v]) q.push(v);
}
}
}
int main()
{
n = read <int> (), m = read <int> ();
for(int u, v, i = 1; i <= m; i++)
{
u = read <int> (), v = read <int> ();
in[0][v]++, in[1][u]++;
adde(u, v, 0), adde(v, u, 1);
}
toposort(0), toposort(1);
for(int i = 1; i <= m; i++)
if((bit[0][e[0][i].to] & bit[1][e[1][i].to]).any()) ans++;
printf("%d\n", ans);
return 0;
}