Chrysanthemum's Blog

首先有一个贪心思想，一条边能删就删，这可以证明是完全正确的。那么，我们只要枚举每条边，u->v，这条边能删的条件就是，u到v还有另外一条路径，这等价于存在另外一个点，u能到达这个点且这个点能到达v，所以我们只要用拓扑排序预处理出每个点能到达的点和能到达每个点的集合，用bitset就可以了。

代码：

#include<cstdio>
#include<bitset>
using namespace std;
int n,m,u,v,edgenum,p1,p2,ans;
int vet[100010],next[100010],head[30010],l[100010],r[100010],ru[30010],q[30010];
bitset<30010> to[30010],fr[30010];
void add(int u,int v)
{
    edgenum++;
    vet[edgenum]=v;
    next[edgenum]=head[u];
    head[u]=edgenum;
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        l[i]=u;r[i]=v;
        add(u,v);ru[v]++;
    }
    for (int i=1;i<=n;i++)
    if (!ru[i]) q[++p2]=i;
    while (p1<p2)
    {
        p1++;
        u=q[p1];
        for (int e=head[u];e;e=next[e])
        {
            int v=vet[e];
            ru[v]--;
            if (ru[v]==0) q[++p2]=v;
        }
    }
    for (int i=1;i<=n;i++)
    {
        to[i][i]=1;
        fr[i][i]=1;
    }
    for (int i=n;i>=1;i--)
    {
        int u=q[i];
        for (int e=head[u];e;e=next[e])
        {
            int v=vet[e];
            to[u]|=to[v];
        }
    }
    for (int i=1;i<=n;i++)
    {
        int u=q[i];
        for (int e=head[u];e;e=next[e])
        {
            int v=vet[e];
            fr[v]|=fr[u];
        }
    }
    for (int i=1;i<=m;i++)
    if ((to[l[i]]&fr[r[i]]).count()>2) ans++;
    printf("%d\n",ans);
}